Yeah, I had to upgrade first and then update with the patch. This took me from 5.0.1 to 5.1.0 and then the patch took me to 5.1.1. My restore worked but I did have to import the server certificate again for some reason, so make sure you export that too just in case!
Also, we have a Guest Manager installation which writes information to the Policy Manager Guest User Repository, but once updated this is written to the Onboard repository. So if you are using Guest User Repository in any service definitions in this way you may need to alter these.