Drupal stores the time at which a node was updated, this is stored in the "changed" field of the node table. This error message is nearly always seen when one user has loaded a node edit form and while they are working on the node another user has loaded the edit form for the same node and submitted their changes before the first user.
Consequently, when the first user submits their form the node_validate() function is called and it begins by inspecting the "changed" timestamp stored in the dtabase against the "changed" timestamp stored inside this users form submission. It determines that the form data is older than the database data and so considers this to be an invalid submission and displays the error message.
However, we have also seen situation, where there is only one user involved working in a single browser tab. In this case there is no opportunity for another sessino to save the node form. It is also confirmed that the user did not save the form and then press their browser back button, nor was there some custom code that manually updated the database without calling node_save() - these are all of the usual suspects that cause this issue.
So far our investigations lead us to believe that there is a condition under which a node (or potentially any entity) can be saved and the entitycache module, if installed, does not update the version of the node that it has cached. Consequently when the user loads their edit form the node is loaded from the entitycache and it is here that we are getting stale data.
Unfortunately we have not yet been able to reliably recreate this problem in order to debug it, but we are working on that and will post a fix back to the Drupal community when we have cracked it.