“Geocode error – request denied” mystery

I have installed the Locatoraid plugin on two WP websites. These websites are hosted by different companies.
I am using different themes but have tested using the same theme and the problem still exists.
I set up Locatoraid EXACTLY the same including the same API key.
One of them works fine. The other will respond to some zip code requests but for other zip codes I get a “Geocode error – request denied” response. There does not seem to be anything unique about the zip codes I use except for the ones that are near me. I have tried zip codes in oregon, california, ny and colorado. Some work others don’t on this one site. The only thing I can think is perhaps it has to do with the hosting server. I would love some help on this.
NOTE: Both these sites have “under development” plugin active but I will gladly provide a WP user and pw along with links to anyone who wants to have a look. These users are not admin… but they will allow you to get in and duplicate the problem.
Thanks