Initially I tried to use a SQL CE database. This seemed the easiest route for publishing and maintenance between my local project and my live site, keeping everything simple and in one place.
However, some settings with my hosting - Rackspace Cloud Sites - caused some issues. I have discovered that this is a common issue, and not one that anyone seems to have resolved. My database connection worked... some of the time. At first I didn't notice the pattern, but it turned out that every time I ran an instance of my site, access to the Umbraco.sdf database file got locked by that instance, so if I tried to access it in a different browser I would get the error message "Umbraco cannot start. A connection string is configured but the Umbraco cannot connect to the database". Repeatedly clearing my cache, cookies and hard refreshing the browser sometimes seemed to reset this locked state, but then if I returned to the other browser, the site would no longer load there. I tried setting permissions on the folder and all the files within it, but this was also disallowed by Rackspace.
I came to the conclusion that I would have to use a different database.
So when moving from SQL CE to a full SQL database I went for the cheaper option, using MySQL for my Umbraco database. However, there are case sensitivity issues between Umbraco and a default MySQL database, because, MySQL is case-sensitive by default, and Umbraco seems to name its tables in camelCase, whilst calling them in UPPERCASE. Therefore it MySQL returns no matching tables. This setting can be switched off by setting lower_case_table_names to 1 in the database. However, if you are working in a shared environment like I was, your hosting provider might be reluctant to change any core settings on the server for you!
In the end, I had to go with MSSQL instead.
This error is due to Umbraco being unable to connect to your database. The reason why can vary greatly - perhaps you just have your connection string wrong? Maybe the database user you are try to access with has the wrong permissions? If you're like me, it stems from the fact that you are using a database other than MSSQL - it's frustrating that all the free options failed me, but you can pick up MSSQL hosting for a reasonable price these days, and its generally considered to much more powerful and future-proof than anything else, so in the long run its probably a good move.
If you had any different reasons for getting this error, post them in the comments!