Hi,
Clean URLs weren't working for me either. I went through what you have suggested and a similar article on drupal.org's forum but it still didn't work. After looking through my httpd.conf I noticed the following entry:

<Directory />
Options SymLinksIfOwnerMatch
AllowOverride None
</Directory>

This directory config block was causing the problem even though I had AllowOverride set to All in drupal's directory config block. Now that I think about it, this behavior _does_ make sense. Anyways, Changing the "AllowOverride None" to "AllowOverride All" in this block brought everything back to normal.

Thanks!
http://www.farhan-ahmad.net