.htaccess problems vs ultimate SEO

This is directly related to the .htaccess file, and I need help figuring out what is going on.

Here's the rundown. We are porting our site to a newer server. We are running the Ultimate SEO module.

When we try to go to a URL which has been rewritten, we get the following error:

404 Not Found

The requested URL /store/index.php was not found on this server.

Additionally, a 404 Not Found error was encountered while trying to use an ErrorDocument to handle the request.

If we rename the .htaccess file so that the url is not rewritten, then it works fine.

Here is our .htaccess file content:

##### NOTE: Replace /shop/ with the relative web path of your catalog in the "Rewrite Base" line below:

Options +FollowSymLinks
RewriteEngine On
RewriteBase /store/

# From Ultimate SEO URLs
RewriteRule ^(.*)-p-(.*).html$ index\.php?main_page=product_info&products_id=$2&%{QUERY_STRING} [L]
RewriteRule ^(.*)-c-(.*).html$ index\.php?main_page=index&cPath=$2&%{QUERY_STRING} [L]
RewriteRule ^(.*)-m-([0-9]+).html$ index\.php?main_page=index&manufacturers_id=$2&%{QUERY_STRING} [L]
RewriteRule ^(.*)-pi-([0-9]+).html$ index\.php?main_page=popup_image&pID=$2&%{QUERY_STRING} [L]
RewriteRule ^(.*)-pr-([0-9]+).html$ index\.php?main_page=product_reviews&products_id=$2&%{QUERY_STRING} [L]
RewriteRule ^(.*)-pri-([0-9]+).html$ index\.php?main_page=product_reviews_info&products_id=$2&%{QUERY_STRING} [L]

# For Open Operations Info Manager
RewriteRule ^(.*)-i-([0-9]+).html$ index\.php?main_page=info_manager&pages_id=$2&%{QUERY_STRING} [L]

# For dreamscape's News & Articles Manager
RewriteRule ^news/?$ index\.php?main_page=news&%{QUERY_STRING} [L]
RewriteRule ^news/rss.xml$ index\.php?main_page=news_rss&%{QUERY_STRING} [L]
RewriteRule ^news/archive/?$ index\.php?main_page=news_archive&%{QUERY_STRING} [L]
RewriteRule ^news/([0-9]{4})-([0-9]{2})-([0-9]{2}).html$ index\.php?main_page=news&date=$1-$2-$3&%{QUERY_STRING} [L]
RewriteRule ^news/archive/([0-9]{4})-([0-9]{2}).html$ index\.php?main_page=news_archive&date=$1-$2&%{QUERY_STRING} [L]
RewriteRule ^news/(.*)-a-([0-9]+)-comments.html$ index\.php?main_page=news_comments&article_id=$2&%{QUERY_STRING} [L]
RewriteRule ^news/(.*)-a-([0-9]+).html$ index\.php?main_page=news_article&article_id=$2&%{QUERY_STRING} [L]

# All other pages
# Don't rewrite real files or directories
RewriteCond %{REQUEST_FILENAME} !-f [NC] 
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule ^(.*).html$ index\.php?main_page=$1&%{QUERY_STRING} [L]

BTW....I am not 100% sure that mod_rewrite is compiled into the server, even though it's a newer upgraded server. I am currently working with the network guys to make sure that isn't the issue.