Тот факт, что внешний доступ открыт в настройках базы, не отменяет того, что в настройках firewall на том самом сервере открыт порт.
Порт может быть и отличным от стандартного 3306.
В настройках базы внешний доступ может быть открыт не для всех IP.
Для таких целей, если не имеется доступа прямого на тот сервер (чтобы проверить настройки), берете типичный анализатор пакетов, например, Wireshark, запускаете локально и смотрите, что там у вас на уровне TCP в момент подключения. Ну или, если Linux локально, то можно и tcpdump-ом смотреть.
Пока что эти шаги выполните, напишите что и как, а дальше посмотрим.