Возможно пользователь с которым вы соединяетесь к базе использует криптование паролей введенное с 4-й версии. И вы не можете соединится с базой так как библиотека PHP не поддерживает это нововведение. Можно попробовать поставить ему пароль без криптования через OLD_PASSWORD.
Подробнее:
http://dev.mysql.com/doc/refman/5.1/en/old-client.html
Так, как предположение...