@JohnAskew: Like I said, it's an existing database with other applications reading it, so updating the key structure isn't a real option.

I was just surprised at this limitation of EF, since every database I've ever used lets you update the PK column. I wonder what the reasoning is behind this decision. Does EF not track original values like ADO.NET DataColumns do?