Coisas para verificar:

1. O MySQL está escutando em IP público (parece que você fez isso)
2. O MySQL está escutando na porta padrão / você está conectando a mesma porta que está escutando.
3. Existe um firewall em execução na máquina remota? (Eles geralmente são empacotados como padrão nas distribuições) O firewall está configurado para permitir conexões com essa porta?
4. Se a máquina remota estiver dentro de outra rede, há tradução de endereço de rede (NAT) acontecendo entre sua conexão e a máquina final? Se estiver, ela está configurada para permitir a passagem da porta MySQL.
5. É o my.cnf arquivo configurado para permitir conexões de qualquer coisa que não seja localhost 127.0.0.1 IPs - embora seja mais provável que você receba uma resposta de acesso negado, em vez de não conseguir se conectar.