It sounds to me like your host doesn't support path_info URLs. Try turning on the disable_path_info option in your config.inc.php file; this will make URLs slightly uglier but will work around your ISP's configuration.
Public Knowledge Project Team
Don't miss the First International PKP Scholarly Publishing Conference
July 11 - 13, 2007, Vancouver, BC, Canada