I ran into this nasty little bug last week. It didn't show up on my local work station running Windows 7 but it showed up once published to our development server running Windows 2003 Server. It would happen when inserting a record to the database after calling "db.SubmitChanges()"
The root cause was having a "non-integer" key which I rarely use, but this instance was special. I was able to fix it immediately by deleting the association in the LINQ designer. I was lucky because so far I don't need this relationship defined in LINQ.
After the immediate fix I noticed our development server was missing some patches, so I put in a request to have those installed. I haven't yet tested if that fixes the problem but I suspect it will. Also there is this hotfix that may work:
Hope this saves someone else some time!