Hi Kristian,
I have re-imaged the VPS using the Strato image "CentOS6 + Plesk12". Once the machine was ready I ran the updates, this was the output.
login as: root
[email protected]'s password:
[root@h2493123 ~]# /usr/sbin/plesk installer install-all-updates
File downloading...