Yeah did that but the error message was the same apart from it replaced V2 with V3.
Anyway, I have Store Locator working again! I set up a new google account, switched on v2 of the APi which generated a new Key. Added the new key to the plugin and it started working.
I read in a Google group that it could be a problem with the Maps API not authenticating Keys.
I think v2 is supposed to work until May, so hopefully by then the plugin will be updated to v3