Thanks for your help justjennifer. I don't know exactly why this doesn't work, but I have found a way to make this work for me.
This is the HTML that I tried (I have removed the 'View Larger Map' link that google adds) is:
<iframe width="425" height="350" frameborder="0" scrolling="no" marginheight="0" marginwidth="0" src="http://www.google.com/maps?f=q&source=s_q&hl=en&geocode=&q=sydney&aq=&sll=37.0625,-95.677068&sspn=60.935792,64.160156&vpsrc=0&ie=UTF8&hq=&hnear=Sydney+New+South+Wales,+Australia&t=m&z=14&ll=-33.873651,151.20689&output=embed"></iframe>
When I click publish, that snippet turns into this:
[googleapps domain="www" dir="maps" query="f=q&source=s_q&hl=en&geocode=&q=sydney&aq=&sll=37.0625,-95.677068&sspn=60.935792,64.160156&vpsrc=0&ie=UTF8&hq=&hnear=Sydney+New+South+Wales,+Australia&t=m&z=14&ll=-33.873651,151.20689&output=embed" width="425" height="350" /]<br />
But on the site, there is nothing. Notice how this says 'googleapps' in the shortcode whereas on http://en.support.wordpress.com/google-maps/ it has 'googlemaps'
So I made my own shortcode by taking the URL (which you can find in the iframe):
http://www.google.com/maps?f=q&source=s_q&hl=en&geocode=&q=sydney&aq=&sll=37.0625,-95.677068&sspn=60.935792,64.160156&vpsrc=0&ie=UTF8&hq=&hnear=Sydney+New+South+Wales,+Australia&t=m&z=14&ll=-33.873651,151.20689&output=embed
Modifying the domain in the URL from 'www.google.com' to 'maps.google.com' and finishing with:
[googlemaps http://maps.google.com/maps?f=q&source=s_q&hl=en&geocode=&q=sydney&aq=&sll=37.0625,-95.677068&sspn=60.935792,64.160156&vpsrc=0&ie=UTF8&hq=&hnear=Sydney+New+South+Wales,+Australia&ll=-33.873651,151.20689&spn=0.0449,0.062656&t=m&z=14&output=embed]
And it worked!