We found the solution.
First, a little bit about Edit Mode --
The tab strip above the Preview Frame appears to change based on the URL of the page in the Preview Pane having a querystring with its ID in it. If you mouseover a URL in the Preview Frame, you see that it has an "id" param in the querystring.
Normal URL: /my/page/
URL when in the Preview Pane: /my/page/?id=123
Well, in this particular use case, we were generating some HTML remotely through a Web service. So, links on the page that was loaded in the Preview Frame were being generated in another process, and that process had no idea we were in Edit Mode and that we should keep the "id" param on there (it had no idea the page into which it was dumping HTML had "idkeep" in its querystring). So the link was the public link, with no id param. Clicking on the link therefore did not update the tab strip.
If a user is in Edit Mode and navigates the site in the preview frame, the part above the preview frame -- where the "Preview" and "Edit" tabs are -- should update to show the page they have navigated to.
However, on one of my installs, this is not happening. The user enters Edit Mode on the start page, then navigates the site in the preview frame. The area above the tabs stays as "Start Page."
If you click "Edit," you go to editing the Start Page, no matter what page you have navigated too.
Why would this happen?