I have searched every thread I could find for troubleshooting Clean URLs in Drupal 7. One distinction in my case is that this is an upgrade from Drupal 6 and Clean URLs do work for a clean D7 install, on the same server. So, the problem is with the upgrade. I just don't know what that problem is.
They don't work both on my local server (MAMP 2.0, OSX 10.7.5) or the remote server (HostGator).