I was having the same problem with my Godaddy installation. To be clear and so that everything is up to date…
Magento CE Community Edition 184.108.40.206
Current Godaddy Hosting configuration as of 02.04.13
Linux Based Deluxe Hosting
1. Created a new Hosting Database via Godaddy platform.
2. Started my Magento Installation after uploading all of my files via Filezilla
3. Logged into phpMyAdmin using db_name/db_username (they are the same) and the db_password.
4. At the very top of phpMyAdmin after you log in you’ll see the IP Address for the database.
5. Copied and pasted these numbers and points into the field for Host. The same area where the default localhost is already input. Replace localhost with the IP Address found in phpMyAdmin if I wasn’t clear enough.
6. Input the rest of the user and password information in for your database. The same information you used to log into your phpMyAdmin panel.
7. You should be free to move through the rest of the installation after this.
Hope that helps and is simple to understand and follow.