If you're on a Mac, here's how to fix it. This is after tons of trial and error. Hope this helps others..
Debugging:
$mysql --verbose --help | grep my.cnf
$ which mysql
/usr/local/bin/mysql
Resolution: nano /usr/local/etc/my.cnf
Add: default-authentication-plugin=mysql_native_password
-------
# Default Homebrew MySQL server config
[mysqld]
# Only allow connections from localhost
bind-address = 127.0.0.1
default-authentication-plugin=mysql_native_password
------
Finally Run: brew services restart mysql