Como SEMPRE me bato com isso quando vou configurar um novo servidor resolvi documentar!

Edite o arquivo /etc/mysql/my.cnf e dentro de [mysqld] comente a linha:

#bind-address: 127.0.0.1

Entre no MySQL via terminal:

mysql -uroot -pmysql

E execute (onde 123 é a sua senha):

mysql> GRANT ALL PRIVILEGES ON *.* TO 'root'@'%' IDENTIFIED BY '123' WITH GRANT OPTION;
Query OK, 0 ROWS affected (0.00 sec)
 
mysql> GRANT ALL PRIVILEGES ON *.* TO 'root'@'localhost' IDENTIFIED BY '123' WITH GRANT OPTION;
Query OK, 0 ROWS affected (0.00 sec)

Reinicie o MySQL:

sudo /etc/init.d/mysql restart

ou

service mysql restart

Adicione também uma regra no iptables para que seja permitido o acesso remoto na porta 3306 (se alterar a porta padrão do MySQL deve ser alterada a porta neste comando):

/sbin/iptables -A INPUT -i eth0 -p tcp --destination-port 3306 -j ACCEPT

E é isso ai pessoal :)