Cannot connect to database master at SQL server at SERVERNAME. The database might not exist, or the current user does not have permission to connect to it.Several blogs where dealing with the permissions, which I checked, but they were well set. The actual problem was the TCP/IP setting of SQLServer. The TCP/IP protocol for the SQL Server was disabled (default setting on installation). Enabling this setting solved the problem.
Enabling can be done using the Sql Server Configuration Manager. Go to SQL Server Network Configuration > Protocols for MSSQLSERVER (or the named instance name you are using) en check the TCP/IP protocol status. This should be 'Enabled'.
So, if you are running into this error, check the user accounts settings as well as the TCP/IP settings of the SQL Server.
Update (23 August 2012): I just add an extra addition: Make sure that SQL server is listening on port 1433 (Thanks to Suolon)