[eluser]Unknown[/eluser]
I had the exact same issue with upgrading from 1.5.4 to 1.6.0 (and later on 1.6.1) on a Media Temple server. The fix of changing the uri_protocol from "AUTO" to "REQUEST_URI" resolved the issue for me.
And this post didn't make it too clear, but that change can be made in the system>application>config>config.php file, on line #44.