I’m having the same problem. I can’t use the geocode or enter in a longitude/latitude coordinate to generate a new location. I get the same message: REQUEST_DENIED
I am running WordPress v 4.5.3. Is it a compatibility issue? If so, will this be resolved soon?