[eluser]dmorin[/eluser]
First, get ride of all rewrite rules in the htaccess file and start with just making sure it works with php5 and the full url including index.php. Next, open your index.php file and do a
Then, in your config.php file, check what your $config['uri_protocol'] is set to and make sure that it shows up in the dump of the server vars from above.
What hosting provider are you using?