On some servers you actually have to uncomment the "RewriteBase /" line in order for your Clean URLs to work!