I'm on Gentoo Linux, with emerged dev-db/mysql-4.0.22. I couldnt connect to the server from a remote host (with proper privileges and IP/host or % as host) not even with telnet, after all the checks (mysqld running and doublecheck permissions) and some fighting i found the solution (may sound lame), in the mysql configuration file (/etc/mysql/my.conf) comment the line (69):Era tan secillo como comentar en el archivo /etc/mysql/my.conf la línea que dice:
#bind-address = 127.0.0.1
restart mysql (/etc/init.d/mysql restart)
and everything works like a charm:)
Good Luck.
bind-address = 127.0.0.1
/etc/init.d/mysql restart