I have the same problem, wordpress 3.0.1 with Twenty Ten theme activated (but also doesn’t work with new theme i’m building). Default structure works but when I change it to a custom structure i get 404 not found pages.
Did you manage to resolve it or did you re-install? I always seems to have issues with page links in wordpress, last one was a weird double home page and then it messed up the blog page.
I’ve made sure htaccess file is writable but I do know that wordpress didn’t auto update it on my first upload/installation i had to enter the code rewrite code myself.
Also wasn’t sure where i set the ‘AllowOveride’ you mentioned?
No plugins installed.
Any help much appreciated it’s driving me crazy