Yes, this is a common issue - I found a Stack Overflow ticket that is perfect for this:
Cannot connect to MySQL 4.1+ using old authentication
Except... I don't have the privileges to run those MySQL commands on my shared hosting provider (Site5). When I asked them, they told me to screw off since I was accessing it from my local computer (which I do only to test web applications before committing/deploying my code). I am using the newest build of XAMPP on Windows 7 and it has PHP 5.3.5.
At any rate, I do not have root access and cannot change the password. They will not run these commands for me. What can I do?
EDIT: Also, when I enable PHP 5.3.5 on my shared host, the database connections work fine despite the old MySQL version and old_passwords file. I did this by adding a handler in .htaccess and confirmed it through phpinfo(). Is this a remote connection issue?