Just thought I'd add my experience to the thread.
After I applied all the latest updates my servers are:
Source: CentOS 5.8, Plesk 11.0.9 Update #26
Target: CentOS 6.3, Plesk 11.0.9 Update #26
Thanks to the info here I was finally able to get everything migrated by changing the service plan but only after I did an unlock and sync. It was a bit tedious since there is no way, that I know of, to unlock and sync all domains so I had to go into each subscription one by one. Luckily I don't have too many sites or it would have been a real pain.