I just found that Entity Framework (4.0) can stumble on One-To-One relationships if the EDMX's schema storage layer (SSDL) is missing the association that represents the Foreign Key in the database. I suppose this makes sense, but it's only obvious to me in hindsight.
I don't know how my EDMX ended up missing the SSDL association for the Foreign Key, but it was missing. However the the Conceptual Layer had the relationship, so the diagram made it look like it was associated. And because this is a supported scenario, it didn't complain at me that I was missing anything.
When I went to save the records, EF stumbled on the insert. In my case, I had two entities that were related by a "1 to 0..1" relationship. I'm guessing that EF saw this, evaluated the SSDL layer's metadata and decided that order of insert didn't matter. As a result, it inserted them in alphabetical order… and failed. It failed because in my DB, I did have a foreign key.
The fix was to manually add the association into the SSDL layer.
Note: Editing EDMX files by hand SUCKS!