DeadTreeMe: You may not have the old_password problem then.
When you look at the output of phpinfo(), what is the "Client API Version" in the MySQL section?
BTW, if you get the "Error establishing a database connection", then the username, password, or server is wrong in some way. Period. Nothing else can cause that. The old_password problem is basically the password being sent incorrectly by an older version of the MySQL client in PHP.
You can test this sort of thing by making a new PHP file with the following and running it:
$db = @mysql_connect('server', 'username', 'password');
if (!$db) echo "connection failed";
else echo "connection succeeded";
If this code returns connection succeeded, then WordPress will work with the same server, username, and password.