I've tried it all (removing all the packages associated with MySQL) but keep getting stuff like this:

Preconfiguring packages ...
(Reading database ... 142196 files and directories currently installed.)
Unpacking mysql-server-5.1 (from .../mysql-server-5.1_5.1.63-0ubuntu0.11.10.1_amd64.deb) ...
ERROR: There's not enough space in /var/lib/mysql/
dpkg: error processing /var/cache/apt/archives/mysql-server-5.1_5.1.63-0ubuntu0.11.10.1_amd64.deb (--unpack):
 subprocess new pre-installation script returned error exit status 1
Errors were encountered while processing:
 /var/cache/apt/archives/mysql-server-5.1_5.1.63-0ubuntu0.11.10.1_amd64.deb
E: Sub-process /usr/bin/dpkg returned an error code (1)

Here is my drive space map.

root@kyle:/# df
Filesystem           1K-blocks      Used Available Use% Mounted on
/dev/mapper/kyle-root
                      59361428  59021768         0 100% /
udev                   1014052         8   1014044   1% /dev
tmpfs                   409304      1476    407828   1% /run
none                      5120         0      5120   0% /run/lock
none                   1023256         0   1023256   0% /run/shm
/dev/sda1               233191     46888    173862  22% /boot
/dev/md0             1922858288 1048513192 776669500  58% /media/array

The root volume actually only has about 10 gigabytes in use on the hard drive (which has a 60 gig partition). /dev/md0 is a 2 TB raid array.