Works in localhost (WAMP), but not on actual server

[eluser]CodeIgniterNewbie[/eluser]
My CI application works fine on my localhost. However, when I upload it to my server, I get:

404 Page Not Found

The page you requested was not found.

base_url is set dynamically. If $_SERVER["HTTP_HOST"] === 'localhost', then I set base_url to my local configuration. Otherwise, it is set to the location on my server.

I've tried all suggested values for uri_protocol. I also added a "?" to index_page. Default controller displays fine on localhost.

What could be wrong with my setup?