I ended up paying for support and although Parallels didn't fix it themselves for me, they pointed me in the right direction. After a few more hours pulling my hair out, this is the summary of how to fix the issue...
The real problem is php and mysql packages from 3rd party repositories, at some point in the past I added the atomic repository to the yum installer and it was these that was causing the update issues. I think I probably did it to upgrade to PHP 5.3.
1. Find out existing php rpm packages.
# rpm -qa|grep php
2. Delete all php rpm packages
I left all the psa packages but manually removed all the others one by one using command below (the no dependency and all matches flags stop error messages). I had to delete about 11 php packages and 5 mysql packages.
# rpm -e --nodeps --allmatches php-5.3.10-5.el5.art
3. Do the same for mysql packages
# rpm -qa|grep mysql
4. Remove any additional yum repositories
# cd /etc/yum.repos.d/
# ls
atomic.repo CentOS-Base.repo.rpmnew CentOS-Media.repo
CentOS-Base.repo CentOS-Debuginfo.repo CentOS-Vault.repo
You should only have the CentOs repositories listed - rename the atomic.repo so it doesn't get used by yum
# mv atomic.repo atomic.repo.old
5. Clean yum
Clean yum to remove any cached packages
# yum clean all
6. Reinstall mysql
Use the following command to reinstall the mysql group (includes server, client etc.)
# yum groupinstall "MySQL Database"
7. Start mysql and check connection
Restart mysql (it may not have been started)
# /etc/init.d/mysqld restart
Check connection
mysql -h 127.0.0.1 -P 3306 -uadmin -p`cat /etc/psa/.psa.shadow`
At one point in the failed upgrade, Plesk deleted the stored password. If you can't connect and you get an access denied error message then try this kb
http://kb.parallels.com/112492.
8. Reinstall php
Use the following yum command
# yum install php
9. Restart mysql and apache
Just to make sure, I then restarted mysql and apache
# /etc/init.d/mysqld restart
# /etc/init.d/httpd restart
10. Rerun the Plesk repair install
Use the bootstrapper command to re-run the plesk install
# /usr/local/psa/bootstrapper/pp10.13.4-bootstrapper/bootstrapper.sh repair
The name of the subfolder 'pp10.13.4-bootstrapper' depends on the version of plesk you are upgrading to. This should now run without errors - be patient it might take a few moments to complete.
11. Check Plesk is working
Login to the control panel and make sure you can access everything
12. Check hosted sites
My static sites were now up and running but my Joomla sites were showing an MySQL adapter connection error. The server at this point really does only have the very basic php and mysql packages.
13. Install additional packages
The main one I needed to get Joomla up and running was php-mysql. Run yum to install:
# yum install php-mysql
14. Update PHP
I did run into a few problems on newer Joomla sites as Joomla 2.5 requires at least 5.2.4 and yum installs 5.1. Having got everything running I then removed php using steps 1 and 2 above and re-installed a newer version of php using:
# yum install php53
# yum install php53-mysql
Hopefully that's helped someone else - it took me about 24hrs to get the server up and running again! However, Plesk 10.4.4 does have the security update which forced me to start the update process initially.