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
added:
Since 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 /var/lib/dpkg.
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:
libdbd-mysql-perl
libdbi-perl
libhtml-template-perl
libnet-daemon-perl
libplrpc-perl
mysql-client-5.1
mysql-client-core-5.1
mysql-server
mysql-server-5.1
mysql-server-core-5.1
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
done
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:
cd /var/cache/apt/archives
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.