I Installed SQL Server 2012 Service pack 1 yesterday and then I started getting the problem you describe in Visual Studio 2012. Not only with database projects; I could not use the SQL Server Object Explorer, not open sql-scripts and lots of other weird database related errors. Always with the same message:
“This version of SQL Server Data Tools is not compatible with … bla, bla, bla …”
This solution helped me: https://web.archive.org/web/20150315060703/http://blog.wharton.com.au/2012/11/16/sql-server-2012-sp-1-breaks-sql-server-database-projects/
Hope this can help you too
Update:
With the March 2013 Release it seems you have to also update the SQL Server Data Tools available here See the comments in this post for more details.