Solution 1:

Some packages can't be uninstalled if some dependencies are gone, or some configuration files have been deleted for some reason. You will end up with a package that is not completely installed nor completely uninstalled.

The solution, in this case, is to sudo apt-get install the package. If necessary, do sudo apt-get install --reinstall [package]. Missing files will be added to the system, and any missing dependencies installed on the fly. Then the package can be uninstalled completely in the usual way: sudo apt-get remove [package].

If apt-get refuses to re-install the package because of other (dependency) issues, you can only use apt-get to download the package and use dpkg directly to install it:

apt-get download mysql-common
sudo dpkg -i mysql-common_*.deb
sudo apt-get install -f

Sometimes you can skip the download because Apt tends to keep an archive of previously downloaded and installed packages in /var/cache/apt/archives/ so you can start directly from the 2nd step:

sudo dpkg -i /var/cache/apt/archives/mysql-common_*.deb