Slave Access Denied Problem

[Andy Theuninck]

Slave server can connect to master server just fine via CLI. When connecting via CLI and issuing SHOW GRANTS the slave user has REPLICATION SLAVE on the master server. When I run CHANGE MASTER on the slave server with the exact same credentials, I get I/O Error 1045 Access denied for user 'slave_user'@'ip_address' (using password: YES).

I have verified that the username and password are in fact correct. They work using mysql -u slave_user -pslave_password -h master_server.

When I connect to the master server as above and run SHOW GRANTS I get this:
+--------------------------------------------------------------------------------------------------------------------+
| Grants for slave_user@% |
+--------------------------------------------------------------------------------------------------------------------+
| GRANT REPLICATION SLAVE ON *.* TO 'slave_user'@'%' IDENTIFIED BY PASSWORD 'hash redacted' |
+--------------------------------------------------------------------------------------------------------------------+

In mysql.user on the master server, there is only one record for slave_user with host %.

I'm out of ideas. The credentials appear to be correct. The permissions appear to be correct. It does not appear to be an issue related to the user's hostname/IP. Why else could it be throwing an access denied error?