My problem is this command produces an error when I tried to connect from our server to another external server :
mysql -h db.hostname.com -u username -pP@ssword database_name
And this is the error :
ERROR 1044 (42000): Access denied for user 'username'@'%' to database 'database_name'
I already asked the external server admin to add our IP in their firewall but to no avail..
Has this something to do with GRANTing privileges to the 'username'
It's not a problem with firewall, since MySQL is denying the connection. As you suspect, it is a problem with the privileges granted for the user. You need to execute this on the mysql server (you might need to tweak this a bit if you don't want to grant all privileges to the db):
GRANT ALL ON database_name.* TO 'username'@'%' IDENTIFIED BY 'P@ssword';
Also note that if you always connect from a specific host/ip, it's a better idea to specify that host/ip, instead of using a wildcard %, which would allow connections from anywhere.