we're using WP 3.4.1 and set up a naked installation to make sure the following is reproducible.
The Sitemap.xml generation doesn't work if you use Polylang along with WordPress SEO. Requesting
sitemap_index.xml results in a redirect (302) to the homepage.
Yoast and Chouby, please shake hands ;-)