If you're doing a clean install, could I recommend Xubuntu Feisty with the new MythTV? I just upgraded mine for the same reason and had no issues.
It sounds like you might be missing a repository. I know you're running a debian based install and I'm running and ubuntu based install, so don't use my exact apt source.list, but here's mine to compare with yours. Maybe you can find a missing repository and set it for the debian files for your release.
[QUOTE]
# See
http://help.ubuntu.com/community/UpgradeNotes for how to upgrade to
# newer versions of the distribution.
deb
http://us.archive.ubuntu.com/ubuntu/ feisty main restricted universe multiverse
deb-src
http://us.archive.ubuntu.com/ubuntu/ feisty main restricted
## Major bug fix updates produced after the final release of the
## distribution.
deb
http://us.archive.ubuntu.com/ubuntu/ feisty-updates main restricted universe multiverse
deb-src
http://us.archive.ubuntu.com/ubuntu/ feisty-updates main restricted
## N.B. software from this repository is ENTIRELY UNSUPPORTED by the Ubuntu
## team, and may not be under a free licence. Please satisfy yourself as to
## your rights to use the software. Also, please note that software in
## universe WILL NOT receive any review or updates from the Ubuntu security
## team.
deb
http://us.archive.ubuntu.com/ubuntu/ feisty universe
deb-src
http://us.archive.ubuntu.com/ubuntu/ feisty universe
## N.B. software from this repository is ENTIRELY UNSUPPORTED by the Ubuntu
## team, and may not be under a free licence. Please satisfy yourself as to
## your rights to use the software. Also, please note that software in
## multiverse WILL NOT receive any review or updates from the Ubuntu
## security team.
deb
http://us.archive.ubuntu.com/ubuntu/ feisty multiverse
deb-src
http://us.archive.ubuntu.com/ubuntu/ feisty multiverse
## Uncomment the following two lines to add software from the 'backports'
## repository.
## N.B. software from this repository may not have been tested as
## extensively as that contained in the main release, although it includes
## newer versions of some applications which may provide useful features.
## Also, please note that software in backports WILL NOT receive any review
## or updates from the Ubuntu security team.
deb
http://us.archive.ubuntu.com/ubuntu/ feisty-backports main restricted universe multiverse
deb-src
http://us.archive.ubuntu.com/ubuntu/ feisty-backports main restricted universe multiverse
deb
http://security.ubuntu.com/ubuntu feisty-security main restricted
deb-src
http://security.ubuntu.com/ubuntu feisty-security main restricted
deb
http://security.ubuntu.com/ubuntu feisty-security universe
deb-src
http://security.ubuntu.com/ubuntu feisty-security universe
deb
http://security.ubuntu.com/ubuntu feisty-security multiverse
deb-src
http://security.ubuntu.com/ubuntu feisty-security multiverse
[QUOTE]
Here's a copy of my root .bash_history file to show how I upgraded ...
[QUOTE]
mysqldump -u mythtv -pmythtv mythconverg -c > mythtv_backup_0709050825.sql
mysqldump -u mythtv -p mythtv mythconverg -c > mythtv_backup_0709050825.sql
mysqldump -u mythtv mythconverg -c > mythtv_backup_0709050825.sql
mysqldump -u mythtv -p mythtv mythconverg -c > mythtv_backup_0709050825.sql
exit
passwd mythtv
mysqldump -u mythtv -p mythtv mythconverg -c > mythtv_backup_0709050825.sql
exit
mysqldump -u mythtv -p lhpwjrig mythconverg -c > mythtv_backup_0709050825.sql
mysqldump -u mythtv -p mythconverg -c > mythtv_backup_0709050825.sql
mysqlcheck -u root -p --repair mythconverg -1 recordedseek
mysqlcheck -u mythtv -p --repair mythconverg -1 recordedseek
mysqldump -u mythtv -p mythconverg -c > mythtv_backup_0709050825.sql
echo "mysqldump -u mythtv -p mythconverg -c > /root/mythtv_backup_0709050825.sql" > MythBackup.sh
chmod a+x MythBackup.sh
nano MythBackup.sh
./MythBackup.sh
exit
./MythBackup.sh
apt-get update
apt-get upgrade
apt-get install mythbrowser
exit
nano /var/lib/dpkg/info/mythtv-backend.prerm
sudo apt-get dist-upgrade
exit
[QUOTE]