Milestones vs. User Stories
The very-critical thing that I meant to say, at the beginging of the above answer, was this:
If your developers need to embark on a multi-step development advance that is of some complexity such that they wish to break it down into milestones apart from "user stories," then I suggest that they should create tests as they are developing the code. (As well as any necessary "stubs" and so on.) The milestone is reached when all of their tests are passed, and they move on from that point while constantly checking that the tests continue to pass, so they know immediately if they just broke something. From time to time, they may retire one of their tests. I present these as separate from the activites of a QA team which is focused on "what will finally be visible out-the-door." All of the foregoing – "Test-Driven Development" – might well be the purview of the development manager, not the higher-level project manager, and seen as being parallel to ("user acceptance" oriented ...) QA.
There are two tiers of "assurance" going on here at the same time – both very similar, yet very different. But the project manager must be at all times aware of what is going on at both levels. And, the two levels should be distinct!
In my opinion, then – the two levels are not (yet) distinct. If there were, then a "release-candidate release process from the development team" would very clearly be in place, and there would be no question as to what the "code to be QA-approved" consisted of.
The specific reason why "the two levels are not (yet) distinct" is exactly as the edited-out paragraph stated: in a software project of any size, there must be two distinct tiers. The QA-team, operating entirely at level-two, should not be involved in – nor, in any way impacted by – the internal (but very necessary) processes that might be happening downstairs at level-one. But the development teams should also never be releasing "candidates" up to level-one QA until they are sure.
My suspicion is that the development team is "racing ahead," from one milestone known only to itself, to another, somehow expecting the QA team to evaluate a target that is moving under its feet. Obviously this is nonsense.
Task Breakdowns and QA Workflows
In addition, I see from your description that the functionality which your QA team is supposed to test is not on a stable version-control branch that will not be affected by future development activities. Developed material should be added to QA branch(es) and tagged so that QA is always testing against a non-moving target.
But also: when you say that "a future story breaks an earlier one," then I would say that you have a much larger task-breakdown problem. "Stories" are supposed to represent what a hypothetical user sees, but they also should reflect the behavior of the to-be released application, not an intermediate step.
"Stories" do have to be composed into what will be the actual workflows and milestones four your development teams – they might not exactly coincide because "story-tellers don't necessarily know how it works." What actually drives your development schedule should be a sometimes-parallel pursuit of completed features, which can then be meaningfully tested such that "regression" from that tests-passed state is not to be expected. It is possible that a single development-workflow increment might complete "part of a story," or "part of several stories." In practice, the architecture of the application – particularly that of a legacy application – dictates this.