That scenario has been reported many times.
Problem stems from the fact that pre-boot works with cached credentials. Those are obtained after SUCCESSFUL sync with EE server.
I think that major source of above trouble is user ability to change password offline (i.e. without talking to the EE server first). I would call it a design flaw.
So depending on sequence of events (on multiple computers) various situations occur. Also, sync seems to update user object in database, based on password change event, regardless when that change occured.