This is the kind of error I was seeing...
Google actually blogged about this change not long ago.
* We no longer support keyless access (any request that doesn't include an API key). Future product updates are only available for requests made with an API key. API keys allow us to contact developers when required and help us identify misbehaving implementations.
Ok great, so you just have to get the key it seems! I noticed that requests for old URLs that have already accessed Maps API data worked, but any new URLs failed. In addition it looks like localhost access to the API doesn't work very well now, even when using a key.
So what you need to create is a browser key. Google has a page describing how to get the API key. If you click the 'Get a Key' button it will take you through the right steps.
First you will be asked to select a project or create a new one.
Then you're taken to the Credentials page where you can generate the key. It's a good idea to give this key a meaningful name as well as add a domain to restrict it to. If the key is unrestricted, other domains can make use of your key, which will reduce your quota allowances i.e. bad things will happen.
After you click 'Create', your new API Key is presented to you.
Making use of your key is easy...
...simply replace 'your_api_key_here' with the actual value of your API Key.
As a bonus for any old URLs the 'no API key' warning will also disappear.