How can I fetch more than 1000 Google results with the Perl Google API?

I don't know a way around this limit, other than to use a series of refined searches versus one general search.
For example instead of just "Tim Medora", I might search for myself by:

Search #1: "Tim Medora Phoenix"
Search #2: "Tim Medora Boston"
Search #3: "Tim Medora Canada"

However, if you are trying to use Google to search a particular site, you may be able to read that site's Google sitemaps.

For example, www.linkedin.com exposes all 80 million+ users/businesses via a series of nested sitemap XML files: http://www.linkedin.com/sitemap.xml.

Using this method, you can crawl a specific site quite easily with your own search algorithm if they have good Google sitemaps.
Of course, I am in no way suggesting that you exploit a sitemap for illegal/unfriendly purposes.