I’m having the same issue. Most of my posts are scheduled and am wondering if that has anything to do with it?
I’m running WP 2.7 and version 3.1.2 of the plugin. The ‘rebuild sitemap if you change the content of your blog’ is checked.
Thanks for any help,
Colby