.htaccess is writeable and I see changes in the file when I switch the permalink options on and off.
Everything seems to meet the requirements and I have another wp blog on the same account with permalinks working.
I am on a shared hosting account, but have never had problems with wordpress in the past.
I noticed an error log in the directory, I don’t need if this tells anyone anything but here is what was in it:
[08-Feb-2009 22:49:25] PHP Warning: Invalid argument supplied for foreach() in /home/xxxxxx/public_html/cp/wp-includes/rewrite.php on line 286