Assuming you have a valid apikey, the problem may be that Google does not like the LWP::UserAgent user agent string. Does it work if you add this after your call to new (untested):

$geocoder->ua->agent('Mozilla/5.0');
[download]