The first thing to check is that the .htaccess file was uploaded properly when you installed Drupal. The second thing to check if thats fine is the RewriteBase if you are installing on a site which is
this can stay commented out. If you are using
Code:
subdomain.domain.com
I find uncommenting out RewriteBase / makes the clean URLs work.