Do you have mod_rewrite?

Yes mod_rewrite is enabled on the servers.