I was able to get it working with the following settings:
htaccess – I did not modify that file at all.
Wordpress Permalink Settings – custom structure > /%category%/
Woocommerce – Settings > Pages Tab > Permalinks > Product base page > Prepend product permalinks with product category *TICKED*
Currently the site is WP 3.2.1 and Woocommerce 1.3.2.1
The theme I am using was recently upgraded for WP 3.3.x and Woocommerce has released WooCommerce 1.4
Not sure if things will go blooey when I upgrade but I will report back once I give it a shot.
Good luck everyone.
