Erro ao tentar realizar uma conexão a um servidor mysql remoto

Bom dia,

Desenvolvo em PHP há um bom tempo, mas sempre utilizei servers dos provedores, como formatei minha máquina resolvi instalar o ambiente na unha ao invés de usar, xampp, wamp, easy, etc.... vamos ao problema.

Após a instalação, tudo funciona, PHP, Apache, mysql, porém, um de meus sistemas, acessa uma base de dados em um provedor(fora da minha rede claro).

Sempre realizei esta conexão normalmente usando xampp, mas agora com os servers instalados na mão dá a seguinte mensagem:

"mysqlnd cannot connect to MySQL 4.1+ using the old insecure authentication. Please use an administration tool to reset your password with the command SET PASSWORD = PASSWORD('your_existing_password'). This will store a new, and more secure, hash value in mysql.user. If this user is used in other scripts executed by PHP 5.2 or earlier you might need to remove the old-passwords flag from your my.cnf file". mMeu PHP é 5.3.3 e o Mysql é o 5.0.7.

Tenho lido várias baboseiras postadas por aí por isso resolvi fazer um post sério aqui e postar a solução depois pois muitos devem ter esta dúvida e não postaram a solução.
Desde já agradeço

Estou perto !!!!

http://blog.thiagobelem.net/mysql/problemas-de-incompatibilidade-no-php-53/

# A nova biblioteca mysqlnd necessita do uso do novo formato de password do MySQL em 41 bytes (MySQL 4.1′s newer 41-byte password format). Continuar usando o formato antigo de senha (de 16 bytes) fará com que o mysql_connect() e funções similares emitam o erro “mysqlnd cannot connect to MySQL 4.1+ using old authentication.“

Entendi, onde está o problemas, mas não sei como resolvê-lo. Tentei alterar a forma de gerar o hash dos dados de conexão para SHA ao invés de md5, mas não adiantou !!!!

Execute no servidor

SET PASSWORD FOR 'usuario'@'host' = OLD_PASSWORD('senha');