If you got a spare box, you could install phpmyadmin (a webapp, if you have a web server running) or mysql workbench on it, then try connecting using that - should give some info on what's going wrong.

To allow a user to login from any host, use the % wildcard as the allowed hosts parameter on the server setup (it defaults to localhost or . which only allows connections from localhost - usually 127.0.0.1)
Or, use a specific IP to only allow that one to connect, or a subnet, eg 192.168.1.0/24 (you best check that syntax!) to allow anyone from the 192.168.1.* network.