Ok, I got it thanks to tglawe.
I just kept doing an apt-get libapache2-mod-python,etc...
and eventually it installed plesk.
Arg,I spoke too soon. I can login into plesk but some things aren't there. I then ran the Plesk install again:
[root@localhost vz-scripts]# vzpkg install 142 plesk8
Hit
http://autoinstall.plesk.com sarge/all Packages
Ign
http://autoinstall.plesk.com sarge/all Release
Hit
ftp://ftp.de.debian.org stable/main Packages
Hit
ftp://ftp.de.debian.org stable/main Release
Hit
ftp://ftp.de.debian.org stable/contrib Packages
Hit
ftp://ftp.de.debian.org stable/contrib Release
Hit
ftp://ftp.de.debian.org stable/non-free Packages
Hit
ftp://ftp.de.debian.org stable/non-free Release
Hit
ftp://ftp.de.debian.org stable/non-US/main Packages
Hit
ftp://ftp.de.debian.org stable/non-US/main Release
Hit
ftp://ftp.de.debian.org stable/non-US/contrib Packages
Hit
ftp://ftp.de.debian.org stable/non-US/contrib Release
Hit
ftp://ftp.de.debian.org stable/non-US/non-free Packages
Hit
ftp://ftp.de.debian.org stable/non-US/non-free Release
Hit
ftp://ftp.de.debian.org stable/updates/main Packages
Hit
ftp://ftp.de.debian.org stable/updates/main Release
Hit
ftp://ftp.de.debian.org stable/updates/contrib Packages
Hit
ftp://ftp.de.debian.org stable/updates/contrib Release
Hit
ftp://ftp.de.debian.org stable/updates/non-free Packages
Hit
ftp://ftp.de.debian.org stable/updates/non-free Release
Reading Package Lists...
Reading Package Lists...
Building Dependency Tree...
psa is already the newest version.
psa-api is already the newest version.
psa-proftpd is already the newest version.
psa-migration-manager is already the newest version.
psa-courier-imap-add is already the newest version.
psa-qmail is already the newest version.
psa-proftpd-inetd is already the newest version.
libpam-plesk is already the newest version.
psa-courier-imap is already the newest version.
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:
The following packages have unmet dependencies:
libapache2-mod-python: Depends: python-central (>= 0.5.8) but it is not going to be installed
Depends: python (>= 2.4) but 2.3.5-2 is to be installed
psa: Depends: psa-php4-configurator but it is not going to be installed or
psa-php5-configurator but it is not going to be installed