Try going a level below apt, after backing up your databases:
sudo dpkg -r mysql-server
sudo apt-get check # verify that apt's metadata is okay
sudo apt-get install mysql-server
dpkg -r is choking try
dpkg --purge and failing that get the package contents with
dpkg -L mysql-server-5.1 zap them and then muck about in
I've never seen things get that hairy, sorry.
if at first you don't succeed
I'm sorta thinking aloud here, forgive me. The mysql-server meta-package contains or requires these packages:
The meta-data for package management is delightfully decoupled, there are central repositories but the packages stand alone.
/var/cache/apt/archives is where
*.deb files that have been installed live.
First, force dpkg to forget about these packages (at the risk of failure to remove some files that we're going to replace anyway).
for i in mysql-server-core-5.1 mysql-server-5.1 ... ; do
sudo dpkg -r --force-remove-reinstreq $i
Then get the .deb files needed for a full install:
sudo apt-get install --download-only mysql-server
and then try installing them one by one:
sudo dpkg -i mysql-server-core-5.1_5.1.41-3ubuntu12.3_i386.deb
if you have problems there, try:
sudo dpkg -D77777 -i mysql-server-core-5.1... > 2>&1 /tmp/dpkg.log.$$
And try and find the relevant lines out of the zillion in the logfile and post them here. Good luck and godspeed.