1045, "Access denied for user 'username'@'NOT-local' (using password: YES)"

show logins to the server (note that % means anyhost or wildcard)

select user,host from mysql.user;

+-----------+------------+
| user      | host       |
+-----------+------------+
| ajax_guy  | %          |
| joe7      | %          |
| joe8      | %          |
+-----------+------------+

show what grants exist for a certain user.

show grants for 'ajax_guy'@'%';

+----------------------------------------------------------------------
| Grants for ajax_guy@%                                              
+----------------------------------------------------------------------
| GRANT USAGE ON *.* TO 'ajax_guy'@'%' IDENTIFIED BY PASSWORD ...
| GRANT ALL PRIVILEGES ON `ajax_stuff`.* TO 'ajax_guy'@'%'           
| GRANT ALL PRIVILEGES ON `ajax_stuff`.`ajax_stuff` TO 'ajax_guy'@'%'
+----------------------------------------------------------------------

How to grant access to a certain db to a certain login. Below we are granting all rights to the user to the so_gibberish database.

grant ALL on so_gibberish.* to 'ajax_guy'@'%';

Look at grants in effect now for that login

+----------------------------------------------------------------------
| Grants for ajax_guy@%                                              
+----------------------------------------------------------------------
| GRANT USAGE ON *.* TO 'ajax_guy'@'%' IDENTIFIED BY PASSWORD ...
| GRANT ALL PRIVILEGES ON `ajax_stuff`.* TO 'ajax_guy'@'%'           
| GRANT ALL PRIVILEGES ON `so_gibberish`.* TO 'ajax_guy'@'%'         
| GRANT ALL PRIVILEGES ON `ajax_stuff`.`ajax_stuff` TO 'ajax_guy'@'%'
+----------------------------------------------------------------------

Create a new login drew_saturday with a password friday987. He has all privileges on database so_gibberish and can login from any host (%)

grant ALL on so_gibberish.* to 'drew_saturday'@'%' IDENTIFIED BY 'friday987';

select user,host,password from mysql.user where user='drew_saturday';

+---------------+------+-------------------------------------------+
| user          | host | password                                  |
+---------------+------+-------------------------------------------+
| drew_saturday | %    | *4600ED0F377308959665877BD327D4788DC2071F |
+---------------+------+-------------------------------------------+

That password above is the hashed password by the way.

Note: for MySQL 5.7 the command above would be:

select user,host,authentication_string from mysql.user where user='drew_saturday';

Mysql manual page on Grant. Do not grant excessive rights to users using grant ALL on *. .... That would be for all database in the system. Just read the manual and less is more.

Sometimes, admins want to grant access to just a handful of tables in a database (not all tables in it) to a login. The manual is a must read on this.

And one last thing. 'drew_saturday'@'%' is a different login than 'drew_saturday'@'NOT-local' (borrowing from your title). They are different logins with different rights. That is the point of the first thing I wrote way up there.