When clients try to connect to MySQL, the server checks username and password and the originating host value against its permissions tables.
This error typically indicates that this username has not been granted appropriate permissions when connecting from this host.
You can fix this by using the command-line mysql tool (on the server host!) to GRANT permissions for the user/hostname combination from which you are trying to connect, and then executing mysqladmin flush-privileges. See this section of MySQL documentation for more details.
If you are running MySQL Version 3.23 or later and you don't know the IP address and/or hostname of the machine from which you are connecting, you can put a wildcard entry with '%' as the Host column value in the user table and restart mysqld with the --log option on the server machine. After trying to connect from the client machine, the information in the MySQL log will indicate the client host's IP address and/or hostname. Important: you should then replace the '%' in the user table entry with the actual hostname that shows up in the log. Otherwise, you'll have a system that is insecure.
A rare cause of this error on Linux is a MySQL binary that was compiled with a newer glibc version than is found on the current binary host. In this case, you should either upgrade your OS/glibc or download the source MySQL version and compile this yourself. A source RPM is normally trivial to compile and install, so this shouldn't be a big problem.