Pode ser uma das 2 coisas abaixo:
O usuário que está tentando acessar, tem privilégios para acesso remoto?
Senão estiver muito confiante para definir em linha de comando, utilize o phpmyadmin para administrar os privilégios de usuário. Você deve dar acesso para todos os servidores (%).
E no arquivo /etc/mysql/my.cnf, tem esse parâmetro:
# Instead of skip-networking the default is now to listen only on
# localhost which is more compatible and is not less secure.
bind-address = 127.0.0.1
Se estiver escutando apenas no localhost, não conseguirá acesso também.
Abraços.