I've found something that works... But I don't understand why.
If I move the first frame of the second story onto the same page as the last frame of the first story, I'm suddenly able to link the frames. Linking the frames loses some of the paragraph styles for some reason, but, if I set these paragraph styles again, then move the frame back where it was on the next page, it stays linked and seems to still work.
The two pages had different master pages, but there were no significant differences in master page settings I was aware of, and they were essentially almost identical, inheriting from the same master page, with a minor difference in running headers. Also, the running headers in the master page of the page containing the last frame of the first story had been overridden, but again I can't see any reason that would make a difference. EDIT: The same thing happened again further on in the document between two pages with the same master page type and no overrides so that doesn't seem to be related.
Testing on a blank document, I have no problem linking stories across pages, so I still don't know what could have caused it to not work in this case - but temporarily moving frames on to the same page then moving them back seems to work.
If anyone can explain why InDesign (CS6) wouldn't link from one page to another even though it could maintain exactly that link across the pages, I'd appreciate that.
Is there something in front of the frame that is blocking it?
If by in front you mean above in the z-index stacking order - some element on top of the frames - that's something I checked for. There was nothing, and, to be doubly sure, I also created a new empty text frame off the page on the pasteboard and linked into that. After it had been successfully linked into from one side, it couldn't be linked into from the other (same result in both directions).
If by in front you mean before in the document flow (y axis?), like an element between the first story and the next story that stopped them linking, then maybe, I wasn't aware that this sort of blocking was possible. What sort of object could block linking like this? There were a few vector shapes above (Y) and behind (Z) the first heading text frame of the second story at the top of its page - is it possible that these can somehow get in the way? I had similar shapes elsewhere in the document without any trouble, but maybe there was a tiny difference in this case that made all the difference.