You may have Overrides turned off on that server, that would prevent .htaccess from even being loaded. Did you check to see if .htaccess is indeed being parsed at all? Perhaps put:
ErrorDocument 404
http://www.google.com/
then hit a document you know doesn't exist and see if it actually goes to google or if it is being overridden elsewhere.
mod_rewrite would return a 500 error if you have RewriteEngine on, and mod_rewrite isn't loaded... provided .htaccess is being parsed.
Can you post the rule so we can take a look? It is probably something like:
RewriteEngine on
RewriteCond %{REQUEST_FILENAME} !-f
RewriteRule ^(.+)\.html$ /index.php/$1 [L]
Its possible that your host has loaded mod_security, in which case you might need to chmod 644 the .htaccess file so that it won't be skipped.