Something could be fudge from the download. Who knows. I suggest starting fresh.
Backup your files. Make sure you are in your html root folder. Connect via ssh if you can, and not telnet (no security with telnet).
cp -a wordpress wordpress.bak
Just to be on the safe side, I would recommend you redownload http://wordpress.org/latest.tar.gz to your server.
wget ht tp://wordpress.org/latest.tar.gz
remove the space between the t's.
And untar it again.
tar -zxvf latest.tar.gz
Then double check your wp-config.php. I suggest replacing it from wp-config-sample.php. First change to the wordpress dir.
cd wordpress
cp -af wp-config-sample.php wp-config.php
Then edit your wp-config.php file. I typically use vi. Use whatever you prefer.
vi wp-config.php
As you know, 4 key values there.
If the above doesn't work. There must be some kind of connection timeout or something. Perhaps your host needs to adjust my.cnf, or php.ini, or even httpd.conf. They all have their own settings for connection timeouts. Maybe something is out of whack. I'm just speculating. Perhaps you can look up log files for mysql. Or did you?
It might be helpful if you could provide the version numbers of mysql, php, and apache.