Host 'xxx.xx.xxx.xxx' is not allowed to connect to this MySQL server

This should be dead simple, but I cannot get it to work for the life of me.
I’m just trying to connect remotely to my MySQL server.

connecting as

mysql -u root -h localhost -p  

works fine, but trying

mysql -u root -h 'any ip address here' -p

fails with the error

ERROR 1130 (00000): Host ''xxx.xx.xxx.xxx'' is not allowed to connect to this MySQL server

In the mysql.user table, there is exactly the same entry for user ‘root’ with host ‘localhost’ as another with host ‘%’.

I’m at my wits’ end, and have no idea how to proceed. Any ideas are welcome.