You probably have just the MySQL-Client... not the MySQL-Server. You need to apt-get that file (and the dependancies) or use synaptic to get them. I am using the "testing" versions of all the .deb files, so it naturally updated the MySQL-Client as well for me. Hope this helps.

Chaz B