I got an error "Key not valid for use in specified state" when I tried to add a new db connection in a database project under Visual Studio 2005.
The soln is to delete all the invalid database connections / references (ie. those with red crosses) and u can create a new db connection again.
Got this answer to my problem in http://forums.microsoft.com/MSDN/ShowPost.aspx?PostID=199339&SiteID=1