STSADM site collection restore error: Access Denied

You're trying to restore a site collection from a backup and you get this error: Access Denied. It's not the more useful "Access is denied. (Exception from HRESULT: 0x80070005 (E_ACCESSDENIED))" which gives you an exception code and subsequently hundreds of blog posts that explain the error. Well, it's still the same problem; you don't have access to the content database. So why is the error message different? It's Microsoft.
Ironically, if you do a backup instead of a restore you'll get a more useful error message:

This message tells you that you don't have access to the content database.

So what can you do? Either give yourself access to the database, or run stsadm using the central admin service account (this is assuming that you're using service accounts and not the local "Network Service").