I'm having the same problem, but i have resolved this by removing installes PSA Packages.
I'm using Debian 4.0 Etch amd64. (64Bit)
I NEVER use "apt-get upgrade" to upgrade the Plesk installations that i manage - i always use the autoinstall script for upgrades.
NOTE: You should make a complete backup of all your data, just to be on the safe side. By executing the commands below, will NOT delete your data - it will just remove the Plesk software, and re-install it all.
I have encountered the problem that this thread describes, and i resolved it by doing the following.:
Edit /etc/apt/sources.list
# vi /etc/apt/sources.list
Remove ALL sources to plesk.com or any other Plesk related download-source. Insert the following:
deb
http://autoinstall.plesk.com/debian/PSA_8.4.0 etch all
Save the file, and execute:
# apt-get update
Check the installed packages, and versions by using:
# dpkg -l |grep -i psa
After running the "apt-get update" command, there might be an error where you need to execute: "apt-get -f install" to fix the system. This might remove the Plesk software, and you should do so.
If the above command did not remove the Plesk software, you need to do this your self by executing the following: "apt-get remove psa"
Again, you need to edit the file /etc/apt/sources.list, and remove the source that we just inserted.
After this, you need to execute: "apt-get update; apt-get upgrade".
After the software has been removed, you can just download the latest "autoinstaller" from:
http://www.parallels.com/en/download/plesk86/ and install the Plesk software again, just as a new installation.
After the installation has been completed, your system is up and running again - and ALL your data, websites, databases, mail etc.etc., is still intact.
** I have had the problem on 8-10 Plesk servers, and the above fixed everything - so my server is working perfectly again.
**
Hope that you can use this.