I just rebuilt my sitemap manually and looked at the serverlogs while doing it. Google fetched the sitamap just before the call to rebuild it, so it seems the notification goes out first and the rebuild takes place afterwards. Google is very fast and even though the rebuild only takes half a second.. Here's the log:
66.249.72.114 - - [15/Jan/2011:00:02:41 +0100] "GET /sitemap.xml.gz HTTP/1.1" 200 1283 "-" "Mozilla/5.0 (compatible; Googlebot/2.1; +http://www.google.com/bot.html)"
n.n.n.n - - [15/Jan/2011:00:02:41 +0100] "GET /wp-admin/options-general.php?page=google-sitemap-generator%2Fsitemap.php&sm_wpv=3.0.4&sm_pv=3.2.4&sm_rebuild=true..
http://wordpress.org/extend/plugins/google-sitemap-generator/