I don't know for certain but I think your conclusion is correct. Basically, once you have changed the certificate on the server, all your managed devices need to be enrolled again, as if they're enrolling with a different Profile Manager server.
But this only raises other questions. For instance, what if you had previously set Profile Manager to lock down the device such that the old enrollment profile can't be removed by the user ? Will it actually allow the device to be registered with the 'new' manager without a complete wipe ? The only way to do this faultlessly would seem to be to prepare for a certificate change by 'releasing' all devices before you change the certificate. Which is a poor way to do things.
The one good point is that there's no real reason you should change your cert every two years. When requesting your cert you can ask for one with as long an expiry date as you want. Renew once every ten years if you want. However, the general feeling is that more frequent changes are better.
Thanks for confirming my suspicion but am surprised there aren't more complaints about this process. Does it happen with all MDM providers if they opt for a 2 year certificate renewal? Devices can be restored to new profiles but connected via USB so are physically touched. A complete wipe would be needed for those with permanent profiles.