I was getting exactly the same error message, then also an error that the connection string was incorrect.
It took me a while to realise what my problem was.
In the web.confing file I used the following to get it working
<add key="SiteSqlServer" value="Server=servername.domainname.co.uk;Database=dnn;uid=sa;pwd=password;" />
<add name="SiteSqlServer" connectionString="Server=servername.domainname.co.uk;Database=dnn;uid=sa;pwd=password;" providerName="System.Data.SqlClient" />
The problem was that I replaced Server=(local) with Server=(servername). So when I removed the brackets and specific the hostname it worked! A silly simple error, but one which I think could be added to the comments of the web.config file.
It should work fine with just the hostname instead of the fully qualified domain name, and don't use the sa, I used that whilst trying to work out what was going wrong. I also tried deleting and recreating the database too.
I hope this helps other people.