I have posted about this before but it had to do with a site I transfered over. This time around it is a new site and there is no reason permalinks shouldn't work
What I have found is that the servers for the sites that the permalinks are NOT working is:
SERVER_SOFTWARE Apache/2.0.54 (Debian GNU/Linux) FrontPage/188.8.131.5235 mod_ssl/2.0.54 OpenSSL/0.9.7e
But the server with the site with permalinks WORKING is:
SERVER_SOFTWARE Apache/1.3.37 (Unix) mod_tsunami/3.0 FrontPage/184.108.40.20634
Could the Apache server software version be the issue?