It sounds like a network problem to me, try a telnet from the app server:
telnet <remote db name/IP> 3306
If that fails, you have a network/firewall problem. Or the DB is is not listening on that port or on the network entirely. Do a netstat on the remote DB to confirm: Linux
netstat -an | grep LISTENING
Or windows
netstat -an | find "LISTENING"
You should see :3306 if it's listening on the default port.