I am having the same problem described above, but mine is a wordpress.com site: http://wonkgonewild.wordpress.com.
I paste the following iframe code from google:
<iframe width="425" height="350" frameborder="0" scrolling="no" marginheight="0" marginwidth="0" src="http://maps.google.com/?ie=UTF8&ll=37.0625,-95.677068&spn=39.371738,86.572266&t=m&z=4&vpsrc=1&output=embed"></iframe><br /><small><a href="http://maps.google.com/?ie=UTF8&ll=37.0625,-95.677068&spn=39.371738,86.572266&t=m&z=4&vpsrc=1&source=embed" style="color:#0000FF;text-align:left">View Larger Map</a></small>
When I save draft or publish wordpress.com converts the code to this:
<a href="http://maps.google.com/?ie=UTF8&ll=37.0625,-95.677068&spn=39.371738,86.572266&t=m&z=4&vpsrc=1&output=embed">http://maps.google.com/?ie=UTF8&ll=37.0625,-95.677068&spn=39.371738,86.572266&t=m&z=4&vpsrc=1&output=embed</a>
<small><a style="color:#0000ff;text-align:left;" href="http://maps.google.com/?ie=UTF8&ll=37.0625,-95.677068&spn=39.371738,86.572266&t=m&z=4&vpsrc=1&source=embed">View Larger Map</a></small>
Which does not look like the shortcode example shown in the wordpress support here: http://en.support.wordpress.com/google-maps/
Indeed, the embedded map does not display correctly, instead a link to my google map is displayed.
I have tried clearing my cache and browsing history and using Chrome instead of Firefox to generate the code as suggested in a similar forum thread. Any other suggestions?