Bem, a resposta foi estúpida, mas simples, SElinux era o problema, e não no servidor de banco de dados, mas no lado do cliente.

No lado do cliente você pode executar:
getsebool -a | grep httpd_can_network_connect_db

Recebi a resposta:
httpd_can_network_connect_db --> off

Para alterá-lo, você pode executar:
setsebool -P httpd_can_network_connect_db on

Depois de fazer isso, o phpMyAdmin conectou-se imediatamente em uma atualização de página.

Eu não tinha ideia de que o SELinux pararia as conexões de saída :(