I was running into this problem with the clean url's producing Server 500 errors with a new webhost and and they modified these rules in the .htaccess file:

  # Rewrite current-style URLs of the form 'index.php?q=x'.
  RewriteCond %{REQUEST_FILENAME} !-f
  RewriteCond %{REQUEST_FILENAME} !-d
  RewriteRule ^(.*)$ index.php?q=$1 [L,QSA]

inserting the '/' as per:

  # Rewrite current-style URLs of the form 'index.php?q=x'.
  RewriteCond %{REQUEST_FILENAME} !-f
  RewriteCond %{REQUEST_FILENAME} !-d
  RewriteRule ^(.*)$ /index.php?q=$1 [L,QSA]

and it worked fine. Still trying to figure out what in their apache config might be different from the norm.