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.

To fix:

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.