More specifically:
Log into your site admin
Components > sh404SEF > Configuration > Extensions Configuration
Go to the Virtuemart tab
Turn "Insert product ID in URL" on.
Where you have variations of products as seperate products (as opposed to a single product with attributes) this will now insert the ProductID value in the URL, so changing the product selector will switch to the different product's URL.
Once done, purge your URL cache, and you should find the problem cleared.
Another problem that can arise that is related to this (though didn't effect Martin's site in this case) is where you have products that are assigned in Virtuemart to multiple categories. What happens as the default is that they will all have the same URL, and will be aliases of whichever is the first URL created.
To set it to show individual URLs for each category (usually you want this if you're showing the category name in the URL) you need to do the following:
Log into your site admin
Components > sh404SEF > Configuration > sh404SEF Configuration
Go to the Very adv. tab
Search for "Virtuemart" and you should find the following:
// SECTION : Virtuemart plugin parameters ----------------------------------------------------------------------------
// set to 1 for products to have requested category name included in url
// useful if some products are in more than one category. By default (param set to 0),
// only one category will be used. If set to 1, all categories can be used
$shDefaultParams['SH_VM_ALLOW_PRODUCTS_IN_MULTIPLE_CATS'] = 0;
Change the value to 1, then save the changes, purge your URL cache and you should now have individual URLs for products in their various categories.
Note that the reason for this setting is due to the implied risk of having duplicate content penalties in Google. If this is of concern to you, research if further. In the few instances I've used it, it's not caused any great penalty, while the benefit to the end user of having the extra categories in the URL is considerable.