I installed v3 Ultimate for two clients. Both currently with only one store. One I have the SEO addon working with no problem. The other the cart will not let me enable the SEO Addon 
The site has another cart in its root directory that is using the RewriteEngine so I know it works on this server. I installed v3 in a new directory called store
My htaccess file is
DirectoryIndex index.html index.php
RewriteEngine on
Pleas note that RewriteBase setting is obsolete use it only in case you experience some problems with SEO addon.
Some hostings require RewriteBase to be uncommented
Example:
Your store url is [url=“http://www.yourcompany.com/store/cart”]http://www.yourcompany.com/store/cart[/url]
So “RewriteBase” should be:
RewriteBase /store/cart
RewriteBase /store
RewriteCond %{REQUEST_FILENAME} !.(png|gif|ico|swf|jpe?g|js|css)$
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . index.php?sef_rewrite=1 [L,QSA]
I have tried all kinds of settings and cannot get v3 to turn on the SEO Addon for this cart. Also, this is on a Network Solutions dedicated server if that helps diagnose problem.