First, edit the map and delete old API Key.
Sometimes a few letters can be left.
Next, check if you write correct domain name while generated API Key. Do you have any redirects?
Copy ALL key and paste into the blank field.
It must be OK.

Use the V3 of Google Map API and you don't need the API Key.
http://code.google.com/apis/maps/documentation/javascript/tutorial....

the google map block needs to be re-written for that,

Yeah, I've been thinking about that for months now. As of May of this year, version 2.x of Google's map API was officially deprecated. It shouldn't be too difficult to update the map block, but I don't currently have the time to do it. :-/

-Steve

I updated the map block to work without a key,
and use v3,

I am not to sure if I am allowed to post the code up here as its very much a hack of the Concrete google map,

and I have not tested it as I only use this on my sites so it would need lots of tidying up and comments.

Just Enter the address the, location should Geo-Code and return the co-ords, you can then edit the co-ords if you need to(not tested since my last alteration)

I had the same issue and found that instead of using the google map add on I used the html ad on with a copied code from the 'share' code on google maps.

I typed in the address on google maps and then hit 'share'. It gives you an embed code which you can then resize within the code.

Not sure how this would effect other areas of your project (if any) but this is an option : )

I meant block, not ad on