Bueno, eso significa que en principio, no hay problemas de red propiamente dichos, pero sí problemas de acceso.
¿El servidor tiene abierto el puerto 3306 o sobre cuál se configuró?
Podrías intentar lo mismo que te dice el mensaje del mysqladmin, y correr el TELNET:
De esa forma te aseguras que efectivamente esté corriendo en el puerto indicado.