cannot login to MySQL remotely users and root can log in locally with no problems. No user can login from a remote connection though

from remote:

[root@yoda:~] # mysql -v --host=r2d2.er.com --user=power --password='burp' power
Warning: Using a password on the command line interface can be insecure.
ERROR 1045 (28000): Access denied for user 'power'@'yoda.er.com' (using password: YES)


from server:

mysql&gt; show grants for power@'yoda.er.com';     
+----------------------------------------------------------------+
| Grants for power@yoda.er.com                         |
+----------------------------------------------------------------+
| GRANT ALL PRIVILEGES ON *.* TO 'power'@'yoda.er.com' |
+----------------------------------------------------------------+
1 row in set (0.00 sec)

mysql&gt; show grants for power@'18.61.10.64';
+--------------------------------------------------------------+
| Grants for power@18.61.10.64                            |
+--------------------------------------------------------------+
| GRANT REPLICATION SLAVE ON *.* TO 'power'@'18.61.10.64' |
+--------------------------------------------------------------+
1 row in set (0.00 sec)



mysql&gt; show grants for power@'%.er.com';
+--------------------------------------------------------------------------------------------------------------------------------------------------+
| Grants for power@%.ex-mailer.com                                                                                                              |
+--------------------------------------------------------------------------------------------------------------------------------------------------+
| GRANT ALL PRIVILEGES ON *.* TO 'power'@'%.er.com' IDENTIFIED BY PASSWORD '*333333333333333333333333333333' WITH GRANT OPTION |
+--------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)


There are no errors in the logs other than access denied. There is no firewall and other services like apache work just fine. Port 3306 is live. (obviously if there are denied logs)
How do I find what is preventing a remote login to mysql?

UPDATE:
my.cnf

[root@r2d2 ~]# locate my.cnf
/usr/local/etc/my.cnf
[root@r2d2 ~]# cat /usr/local/etc/my.cnf

[mysqld]

relay-log=r2d2-relay-bin
log-bin=mysql-bin
server-id=1
general_log_file=/var/log/query.log
max_allowed_packet = 10M
innodb_data_home_dir = /var/db/mysql/
innodb_data_file_path = ibdata1:10M:autoextend
innodb_log_group_home_dir = /var/db/mysql/
innodb_buffer_pool_size = 16M
#innodb_additional_mem_pool_size = 2M
innodb_log_file_size = 5M
innodb_log_buffer_size = 8M
innodb_flush_log_at_trx_commit = 1
innodb_lock_wait_timeout = 50

#replication stuff
log_bin = /var/log/mysql/mysql-bin.log
binlog_do_db = powerdns
ssl-key=/home/opensslkeys/server.key
ssl-cert=/home/opensslkeys/server.crt
ssl-ca=/home/opensslkeys/ca.key
explicit_defaults_for_timestamp = 1

bind-address=0.0.0.0


system info:

[root@r2d2 ~]# freebsd-version
10.1-RELEASE-p5

[root@r2d2 ~]# mysql -u root -p -e 'SHOW VARIABLES LIKE "%version%";'
Enter password: 
+-------------------------+---------------------+
| Variable_name           | Value               |
+-------------------------+---------------------+
| innodb_version          | 5.6.27              |
| protocol_version        | 10                  |
| slave_type_conversions  |                     |
| version                 | 5.6.27-log          |
| version_comment         | Source distribution |
| version_compile_machine | amd64               |
| version_compile_os      | FreeBSD10.1         |
+-------------------------+---------------------+
The problem might be a result of how you are defining your users.  I don't think the wildcards are working as you're expecting them to. The best way to figure this out, in my opinion, is to create a new user and password for the 18.61.10.64 host on the yoda.er.com MySQL Server. 

Keep in mind that when logging in locally, the MySQL client on your server might be using the unix socket to authenticate. 

mysql&gt; show variables like '%socket%';
+---------------+-----------------------------+
| Variable_name | Value                       |
+---------------+-----------------------------+
| socket        | /var/run/mysqld/mysqld.sock |
+---------------+-----------------------------+


Connecting to MySQL

If this is the case then a password isn't necessary when logging in locally onto the MySQL server. 

Could you try this from the machine you are trying to connect to. Use a new user and password combination because we are not sure how many different entries you might have for your power user.

GRANT ALL PRIVILEGES ON *.* TO 'someuser'@'18.61.10.64' IDENTIFIED BY PASSWORD 'somepassword';

FLUSH PRIVILEGES;


Then from the shell on 18.61.10.64

mysql -u someuser -h ip.address.for.r2d2.er.com -psomepassword