With the help of Justin Harrison, the problem has been diagnosed.
The error can be replicated only when on iOS 5.1, and upgrading an app to an updated version. On a new app install, you won't see this.
The bug is that the "WebDatabaseDirectory" and "WebKitLocalStorageDatabasePathPreferenceKey" values from NSUserDefaults (which are effectively read from Library/Preferences/[CFBundleIdentifier].plist) are incorrect, they refer to the previous version's app path.
What's probably happening is, during an app upgrade, the app was moved/renamed to a new GUID, but these two plist values were not updated accordingly. The renaming of the app's application bundle to a new GUID might be new behaviour with iOS 5.1 app upgrades.
The first clue we had was this error in the console log:
deny file-write-create /private/var/mobile/Applications/43A38BD0-439A-4998-A51D-110C6E05AF7C
The simplest explanation: permissions error, but what file? But all files in our app bundle we should have permissions to already.
On application launch, we printed out the value for "WebKitLocalStorageDatabasePathPreferenceKey" from NSUserDefaults, and compared it to the application's bundle path. The value for the key should reside entirely inside the application's bundle path, since this is where Webkit stores the localStorage database (similarly for WebSQL, the location for the database is through the "WebDatabaseDirectory" key).
Everytime we see the permissions error, we see that the value for "WebKitLocalStorageDatabasePathPreferenceKey" contains a path OUTSIDE of our application bundle. Bingo!
On app launch on an iOS 5.1 system, we test the keys "WebDatabaseDirectory" and "WebKitLocalStorageDatabasePathPreferenceKey" from NSUserDefaults, and if the paths fall outside of the application bundle's path - we change the paths to reflect the correct paths within the application bundle.
We then commit the new path changes by reading then writing from the Library/Preferences/[CFBundleIdentifier].plist file, then synchronize NSUserDefaults to pick up the new changes.