I’m having this exact same problem with my newly installed blog. My other blog (that I upgraded to 2.3.5 as well) is running along just fine. I even copied the .htaccess from the working one to the broken one and it still isn’t working.
Clearly mod_rewrite wasn’t working. I fixed the problem by adding:
Options +FollowSymLinks +SymLinksIfOwnerMatch
into wordpress .htaccess .
