SEO Add-on - Billingual Site

I discovered this issue last night and have been working for hours trying to figure this out. I have this code which I believe is required for the SEO add-on:

DirectoryIndex index.html index.php




Some hostings require RewriteBase to be uncommented

Example:

Your store url is [url]yourcompany.com

So “RewriteBase” should be:

RewriteBase /store/cart


RewriteBase /
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]

RewriteCond %{REQUEST_FILENAME} .*\/catalog\/.*
RewriteCond %{REQUEST_FILENAME} -d
RewriteCond %{REQUEST_FILENAME}/index.html !-f
RewriteRule . index.php?sef_rewrite=1 [L,QSA]

Everything works fine however right below that I also have a language redirect:
RewriteCond %{HTTP:Accept-Language} (fr) [NC]
RewriteRule ^$ /fr/ [L,R=301]

RewriteCond %{HTTP:Accept-Language} (en) [NC]
RewriteRule ^$ /en/ [L,R=301]

Everything works fine in Firefox but the issue is in Internet Explorer, the first language that I redirect will work fine, the second (in this case English) won't. The redirect will work but when the user will try to sign-in, he'll go right back to the home page and won't be signed in. If he goes to a page like "Register" or "Checkout" he'll be signed in and he'll be signed in if he changes back to french. However, any category page or product page he won't be signed in.

I tried to switch english and french so that it would look like this:
RewriteCond %{HTTP:Accept-Language} (fr) [NC]
RewriteRule ^$ /en/ [L,R=301]

RewriteCond %{HTTP:Accept-Language} (en) [NC]
RewriteRule ^$ /fr/ [L,R=301]

and the problem is reversed.

I tried inserting rewrite base/ and the next 8 lines between the two but doesn't work either.

Anyone have any suggestions? I'm desperate for help.

Thanks,
Phil