Error: There is a compatibility range mismatch between the Web server and database

There is a compatibility range mismatch between the Web server and database "SP2013_Content_InsertDatabaseNameHere", and connections to the data have been blocked to due to this incompatibility. This can happen when a content database has not been upgraded to be within the compatibility range of the Web server, or if the database has been upgraded to a higher level than the web server. The Web server and the database must be upgraded to the same version and build level to return to compatibility range.

Cause

Discovered the error the first time I tried to upgrade a sandboxed solution within the selected database using PowerShell after upgrading to SP1. The error message appears the script output, Event Viewer and ULS. All databases had "No action required" as upgrade status, so this wasn't the problem in my case. Hidden behind this error it appeared that insufficient database permissions was the cause.

Solution

It turned out that the logged in users' permissions for this database had been lost after upgrading SharePoint 2013 from March PU to SP1 for some reason.

Fixed this was easy by adding the "SPDataAccess" role back to the user for the content database that was failing.