I'm setting up a new site on 3.4.1 and the Permalinks will not work.
I have deactivated all plugins and switched to TwentyEleven and they still fail.
I can see through outputting $wp_rewrite that the rules are being flushed when I chnage the structure, and .htaccess is being updated, but no matter what I do, I just get a 404 error.
I also notice that it doesn't matter what structure I use (excluding default), all links are in the format of the /%postname%/ structure.
Any suggestions of what else I can try? Thanks.

.htaccessfile in your site root? – TheDeadMedic Jul 6 '12 at 11:13.thaccessfile is available and being updated when I change the Permalink structure. Have deleted and ensured that a new one can be created also, and that worked fine. – David Gard Jul 6 '12 at 11:21