mysql-server-5.0 upgrade problem. Unable to install anything.

Yesterday a bunch of updates were available for Mysql and php related stuff, so I upgraded but some problems with mysql started occurring. Aptitude said that it was unable to update due to some errors, but the rest installed fine and it even seems that Mysql upgraded ('mysql --version' gives the up-to-date version). I still keep getting the errors though, and I am unable to update the mysql-server-5.0 package, and due to the problems with that I am unable to install any other packages.

Here's what I get when I try to update mysql:

n$ sudo aptitude dist-upgrade
Reading package lists... Done
Building dependency tree... Done
Reading extended state information
Initializing package states... Done
Reading task descriptions... Done
Building tag database... Done
The following packages will be upgraded:
  mysql-server-5.0
1 packages upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
Need to get 0B/25.6MB of archives. After unpacking 16.4kB will be used.
Do you want to continue? [Y/n/?] y
Writing extended state information... Done
Preconfiguring packages ...
Selecting previously deselected package mysql-server-5.0.
(Reading database ... 63770 files and directories currently installed.)
Preparing to replace mysql-server-5.0 5.0.26-3 (using .../mysql-server-5.0_5.0.2 7-1_amd64.deb) ...
Stopping MySQL database server: mysqld.
/etc/lsb-base-logging.sh: line 42: RUNLEVEL: unbound variable
invoke-rc.d: initscript mysql, action "stop" failed.
dpkg: warning - old pre-removal script returned error exit status 1
dpkg - trying script from the new package instead ...
Stopping MySQL database server: mysqld.
/etc/lsb-base-logging.sh: line 42: RUNLEVEL: unbound variable
invoke-rc.d: initscript mysql, action "stop" failed.
dpkg: error processing /var/cache/apt/archives/mysql-server-5.0_5.0.27-1_amd64.deb (--unpack):
 subprocess new pre-removal script returned error exit status 1
Stopping MySQL database server: mysqld.
/etc/lsb-base-logging.sh: line 42: RUNLEVEL: unbound variable
invoke-rc.d: initscript mysql, action "stop" failed.
Starting MySQL database server: mysqld.
/etc/lsb-base-logging.sh: line 42: RUNLEVEL: unbound variable
invoke-rc.d: initscript mysql, action "start" failed.

At that point it just seems to hang, so I ctrl+c and get this:

dpkg: error while cleaning up:
 subprocess post-installation script killed by signal (Interrupt)
Errors were encountered while processing:
 /var/cache/apt/archives/mysql-server-5.0_5.0.27-1_amd64.deb
E: Sub-process /usr/bin/dpkg returned an error code (1)
A package failed to install.  Trying to recover:
dpkg: error processing mysql-server-5.0 (--configure):
 Package is in a very bad inconsistent state - you should
 reinstall it before attempting configuration.
Errors were encountered while processing:
 mysql-server-5.0

(Note: I have tried to just leave aptitude doing it's thing for an hour or so, but it didn't do anything)

When I try to install something I get this:

$ sudo aptitude install automake
Reading package lists... Done
Building dependency tree... Done
Reading extended state information
Initializing package states... Done
Reading task descriptions... Done
Building tag database... Done
The following NEW packages will be automatically installed:
  autoconf
The following packages have been kept back:
  mysql-server-5.0
The following NEW packages will be installed:
  autoconf automake
0 packages upgraded, 2 newly installed, 0 to remove and 1 not upgraded.
Need to get 0B of archives. After unpacking 3195kB will be used.
Do you want to continue? [Y/n/?] y
Writing extended state information... Error!
E: I wasn't able to locate file for the mysql-server-5.0 package. This might mean you need to manually fix this package.
E: Couldn't lock list directory..are you root?

I tried removing and reinstalling MySQL but it doesn't allow me to do that either.

Is there anyway to override this error and remove MySQL to reinstall it? Does anyone know why this error even occurs? I seriously need help :(

Edit: I managed to at least get Apt to a working state by removing the package entries in the status files under /var/lib/dpkg/. I am still unable to install or remove MySQL though, the major problem appears to be with lsb-base.
I cannot start the MySQL server which still appears to be installed (though it isn't in apt's database) due to an error:

$ sudo /etc/init.d/mysql start
Starting MySQL database server: mysqld . . . . . . . . . . . . . . failed!
/etc/lsb-base-logging.sh: line 42: RUNLEVEL: unbound variable

Could someone please help? I need MySQL for web development :(