WP E-Commerce is full-featured enough that it provides us with a Google Product feed "out of the box". But, at no fault of the WP E-Commerce developers, the feed found in older versions of the product no longer fulfills Google's requirements.
Namely, we're missing the unique product identifier.
If you're somewhat savvy with a code editor, you can modify the source of this file to include the information we need:
/plugins/wp-e-commerce/wpsc-includes/productfeed.php
Keep track of your changes – if you upgrade WP E-Commerce you may need to apply them again.
Around line 174, insert the following, which will satisfy Google's unique product identifier requirement:
$output .= " <g:mpn>" . $product_meta['_wpsc_sku'][0] . "</g:mpn>\n\r";
Obviously, this will only work if you have actually specified a SKU for all of your products.