I couldn't get MySQL Administrator on a Windows XP desktop to connect to a MySQL instance I had running on an Ubuntu 6.06 server that I built as a LAMP server. I was getting:
Could not connect to the specified instance.

MySQL Error Number 2003
Can't connect to MySQL server on 'server' (10061)
I had to edit /etc/my.cnf (or /etc/mysql/my.cnf depending on where yours is stored) on the Ubuntu server to comment out the "bind-address" line, then restart the server. I also had to add a non-root user with all privileges. In fact, you have to add two users as described here:
use mysql
grant all privileges on *.* to 'user'@'localhost' identified by 'password' with grant option;
grant all privileges on *.* to 'user'@'%' identified by 'password' with grant option;
flush privileges;
There are some posts that show how to enable remote logins by the MySQL "root" user, but I prefer not to do it that way.