Hiya Chad,
Give this a shot:
1) Login to cPanel
2) Type 'Remote' into the top left finder, this will bring up the Remote MySQL interface
3) Add the IP address you're attempting to connect from
4) Give it a shot!
You can also consult this, basically has the same instructions: https://support.hawkhost.com/index.php?_m=knowledgebase&_a=viewarticle&kbarticleid=144
This should do the trick for you, as it sounds like you've covered everything else