Our application uses embedded Visualforce pages within standard object pages (contact, lead, account, opportunity).

Since the Summer '13 upgrade, a couple users (in separate orgs) are reporting that the embedded page will fail to load with this error message:

The page you submitted was invalid for your session.  Please click Save again to confirm your change.

Note that "Save" has not been clicked, nor any changes made.  This is on the initial load of the parent page.

The only fix we've discovered so far is to manually delete all salesforce.com and visual.force.com cookies.

This is not a bug in our code; these people are running the exact same version they have been running for years.  The only new thing in the mix is Summer '13.

Salesforce support - I have created case 09431887 to track this issue.