Here are some of the most common reasons why your clean URLs may not be working (assuming you're using a normal Linux/Apache hosting environment).
1. Your site is in a subdirectory, or you're using an Alias, but you didn't set RewriteBase
2. Your .htaccess file didn't get uploaded at all
3. Your .htaccess file is corrupt
4. Pager and other query strings don't work