Rails can't connect to external mysql server despite Privileges

I run rails on my local dev environment but the mysql instance is on a separate server.

When trying to open a page in the app I get this error:

Access denied for user 'username'@'myhostname.lan' (using password: YES)

When I ssh into the server running mysql and run this command SELECT Host from mysql.user WHERE User='username'; I get the following:

+---------------------+
| Host                |
+---------------------+
| %                   |
| myhostname.lan      |
| localhost           |
+---------------------+

All of these entries were created with GRANT ALL PRIVIELEGES ON dbname.* TO ...

So why can I not connect given that both the any-host wildcard % is in the list as well as the hostname I try to connect from specifically?