I hope your problem might have been already resolved.

However, I recently had a similar experience and I had to do following to resolve it.

1. Launch MySQL Workbench (Mine was 5.2.36 CE Revision 8542)
2. Double click on a server instance to manage the server instance
3. Goto Users and Privileges
4. Select root or other user you wish to check from the list in "Server Access Management" tab
5. Change the "Limit connectivity to hosts matching:" to IP that you are using to connect OR just change it to "%" to remove the IP restriction.<6> 6. In my case I had to change it to "%" to make it work.

Hope this will be helpful to someone, someday!
Cheers Manish.

PHP must be expecting to use the old MySQL authentication plugin algorithms. You do not have to restart mysql. Since old_passwords is a globally dynamic option, all you have to do is run the following:

SET GLOBAL old_passwords = 1;

In addition, please add this to /etc/my.cnf:

[mysqld]
old_passwords=1

to have future restarts retain this setting.

To further verify the need to do this, the next time you login to mysql, run this

SELECT LENGTH(password) password_length,COUNT(1) length_count
FROM mysql.user GROUP BY LENGTH(password);

If none of the passwords are of length 16, this may explain PHP's reluctance to login.

Sad to say, but the alternative would be to setup 16-character passwords, but you cannot reverse-engineer 41-character passwords. You would have to manually setup the 16-character passwords using the original plain-text values.

For example, if root@localhost had 'helloworld' as the password, it would have convert it using the OLD_PASSWORD function. Here is a comparison:

mysql> select password('helloworld');
+-------------------------------------------+
| password('helloworld')                    |
+-------------------------------------------+
| *D35DB127DB631E6E27C6B75E8D376B04F64FAF83 |
+-------------------------------------------+
1 row in set (0.00 sec)

mysql> select old_password('helloworld');
+----------------------------+
| old_password('helloworld') |
+----------------------------+
| 6c755a9e66debe8a           |
+----------------------------+
1 row in set (0.00 sec)

mysql>

Once you activate old_passwords, to convert it you would have to do something like this:

UPDATE mysql.user
SET password = OLD_PASSWORD('helloworld')
WHERE password = PASSWORD('helloworld');
FLUSH PRIVILEGES;

UPDATE 2013-02-02 22:44 EDT

If changing the authentication style on the MySQL side has not worked for you at this point, I have some bad news for you. You stated earlier:

I used php 5.2.9 and everything worked ok but lowering php is not a solution for me. I also have to mention that i dont have full access to DB's settings cause the client doesn't give me that full access.

You may need to downgrade PHP after all. If your hosting provider isn't in position or unwilling to adjust MySQL or give you a downgraded PHP, you will have to go with a hosting provider that will.

As an alternative you may want to look into Amazon EC2 when you can have full control of all software upgrades after running sudo -s. The links you mentioned before gave you what you needed to know. I gave you what you can do to accommodate the MySQL side. Do what you know has to be done to get this solved.