For some reason, they only installed .Net 4 on their management servers, and did not have .Net 3.5 installed.
Turns out the installation requires .Net 3.5 to be installed on the management servers, and, despite the prereq check returning no errors, the installation fails on the Management Server component with the following error reported in the install log:
Error: :LaunchMSI: MSI C:\System Center Operations Manager\Setup\AMD64\Server\OMServer.msi returned error 1603
The installation then rolls back, which uninstalls all OpsMgr components on the management server.
If you then try to rerun the installation, it will fail on the database selection screen with an error that it cannot connect to the instance/find the database, but when you look in the Install log the error states that the management server already exists in the database and a recovery is not possible at this time.
You will need to recover the database, remove the management server from the management group and reinstall it to recover.
So, before you upgrade, make sure you take a full backup of the OperationsManager database, and make sure .Net 3.5 has been installed on all management servers.
ps: I am sorry for shamelessly nicking pictures off the interwebs for this post. If these belong to you, please let me know.