Google has been on and off testing maps on right side of the web results, in place of the AdWords ads. In fact, the map itself for me has been on the right side on some searches for a while.
Here is a picture of what I see right now:

Google seems to now be testing putting the map details as shown above in the lower portion of the web results, on the right hand side bar.
Wissam Dandan posted a screen shot on his Google + page of this in action:

This obviously takes away from the ad spots, but when the query is so local specific, it likely makes sense.
Forum discussion on Google +.

Comments:
Baczoni Áron
10/10/2011 08:04 pm
Yeah, its sort of new. I've also seen ads on the bottom of the page, after the organic results when those maps appeared on the right side.
Marketing Ideas-Michael Fokken
10/11/2011 02:07 am
I'm not sure if yours does the same, but my map is on the right as well. However, when there are ads below the map and I scroll down, the map scrolls down the page with me but over the ads.