I had another problem with EF4 today. Code that worked fine in .NET 3.5 didn’t work after I regenerated the entity model using Visual Studio 2010.
I found an answer, again on Stack Overflow: http://stackoverflow.com/questions/2243618/how-do-you-insert-or-update-many-to-many-tables-in-net-entity-framework
It turns out that the generator decided that one of my foreign keys in an associative table should have a StoredGeneratorPattern of Identity, meaning it thought it was an identity column. When it isn’t.
But updating the XML as suggested in the answer above fixed it. So that’s good.