I got this strange issue today, and was struggling to fix this. This issue is related to the SQL 2008 and 2005 compatibility. I had a local machine with SQL 2008, but the Dev environment is with SQL 2005. When i generated the Entities using EF in my local machine it had marked it with 2008 version. When deployed to 2005 the issue was reported.
Open the .edmx file using the XML editor option and look for the attribute ProviderManifestToken=”2008″ and change it to 2005 and save. Build and deploy it works.