Original poster here
I finally got it working after much head scratching. Seems the issues was that it needed to know the proxy (it didn't seem to detect the environment varables). So in the interest of sharing code back to the community

#!/usr/bin/perl
use Geo::Coder::Google;
use Data::Dumper;
use LWP::UserAgent;

my $ua = LWP::UserAgent->new(agent => "Geo::Coder::Google/0.01");
$ua->proxy('http', 'http://myproxy.com.au:80');

my $geocoder = Geo::Coder::Google->new(apikey => '{my api key}', ua =>
+ $ua);
$geocoder->ua->agent('Mozilla/5.0');

  my $location = $geocoder->geocode( location => 'Hollywood and Highla
+nd, Los Angeles, CA' );
print Dumper $location;
[download]

Thanks to those whoi responded that it worked. I at least then knew that the problem was at my end, an not with the module.