Se você tiver um usuário como root @ '%', poderá se conectar. Você deve mudar isso para root@'xx.xx.xx.% 'em vez de root @'% ', já que você não quer acesso remoto tão aberto.
Pode ser necessário verificar as configurações do seu firewall.
Tente isso
service iptables stop
tente conectar-se novamente