Pues yo creo que se estan complicando mucho... el mensaje claramente dice que el usuario al que le quieres dar accesos no está dado de alta en la tabla de usuarios. De manera que primero deberás dar de alta el usuario y luego asignarle los privilegios que quieras. Te recomiendo la aplicacion Navicat, el cual es un front-end para MySQL muy facil de utilizar y que te permite hacer lo que necesitas sin necesidad de teclear comandos...lo malo es que es de paga pero el Demo funciona 30 dias.
Tambien puedes usar el MySQL Admin que ya viene con la db, te permite dar de alta usuarios y todo aunque es mas sencillo.
No te recomiendo PHPMyAdmin, pues no tendrìa caso usarlo en un ambiente como el que mencionas (PHP Admin es mas para Web y cosas asi)
Por ùltimo, recuerda que a cada usuario que crees, le tienes que indicar de que host se va a conectar, de lo contrario MySQL asume que esta en localhost (la maquina servidor) y no da acceso. En el caso que mencionas, escribes como usuario
root@xx.xx.xx.xx lo cual no es un usuario verdadero, por eso no lo encuentra MySQL. Para que un usuario pueda accesar a MySQL desde cualquier lugar (inclusive por Internet) deberàs poner en el campo hots del usuario el caracter "%", que es un comodin. Si deseas que un usuario solo se conecte desde una direcciòn IP siempre, pues escribes esa direcciòn en ese campo y asi ese usuario solo podrá acceder a la db desde esa dirección.
Yo por lo regular asigno el valor % al campo host del usuario root, y asi puedo administrar la db desde cualquier lugar.