Zdalne połączenie z bazą danych mysql Opcje

[Hazo]

Witam!
Mam pewien problem z połączeniem się z mojego komputera z bazą danych na serwerze. Na serwerze, na którym znajduje się baza ustawiłem zdalny dostęp dla każdego użytkownika, no ale próba połączenia się z serwerem nadal wywala taki właśnie błąd:

Warning: mysql_connect(): Client does not support authentication protocol requested by server; consider upgrading MySQL client in c:\usr\krasnal\www\...

Napisałem maila do operatora serwera i dostałem odpowiedź, że coś nie tak musi być z moim serwerem, z którego łącze się z bazą mysql.
Serwer który mam u siebie postawiony to krasnalserv, podobno przyczyną tego problemu może być stara wersja mysql (w krasnalu była 3.23.58) więc zrobiłem aktualizację do wersji 4.1.10 ale nic to nie dało.
Ktoś ma jakieś pomysły jak rozwiązać ten problem?
Z góry dzięki za pomoc.