As of time writing this answer, I've realized it's not about testing, it's about documentation. You should first read agile manifesto:
[We value] working software over comprehensive documentation
So, you should make your specifications executable, i.e. write them as a fully automated set of tests.
Is writing specs based on stories a good idea?
Yes, imho, it is. It's called "behaviour driven development" or "specification by example". In ruby there's a great tool cucumber that helps in that much .
The problem now is that because there's so many stories, it's not immediately clear, for any part of the system which stories relate to it.
Why do you want it to be clear? I mean, do you really need a "test/code" traceability matrix? The advantage of writing tests as a specification is that you don't need a separate "requirements/tests" traceability, because tests become requirements. For the purposes of integration testing you should treat your software as a whole, not as separate parts.
You might need a coverage tool to see if there are "dead" modules, parts of your system not covered by your specification tests. But you really shouldn't care what specification this particular code corresponds to. It should be vice versa: from a particular specification you should know which part of the system corresponds to it. You shouldn't worry about some duplication in your specifications. And if you apply a DRY principle to your code there would be dozens of specs executing the same code.
It works at the time of developers, every sprint the devs just get a spec outlining what they need to do and the changes they need to make. But in terms of maintaining this story list and for testing, its starting to get really hard tracking bugs and in general just maintaining the specs, because one piece of functionality in the screen might have been documented in a number of different places due to it being split by story.
It's not that uncommon that hundreds of integration tests are broken by one little change in a critical module. That's where unit testing steps into.
You should structure your tests as such so that you can tell if a particular test covers a high level requirement, or just a subtle detail of it. If the latter, you should separate this test from your integration tests suite. The purpose of unit testing is to localize bugs. So that if you introduce a bug, there will be one and only one test failure.
Have we written the stories in the wrong way?
I think, you just need to organize your stories into epics either by user, e.g. "Customer", "Assistant", or by features/screens/workflows ("Purchase", "Refund").
And again, specification tests are not a replacement to unit testing. Read more