Änderung der Permalinks erzeugt durchgehend 404

Hallo,

ich wollte die Permalinkstruktur meines WP 3.2.1 Blog ändern und hab das auch gemacht,

von /?p=%post_id%/
auf /%category%/%postname%/

mit dem durchschlagenden Erfolg, dass nun nur noch die Startseite funktioniert, die Artikel bringen 404 not found. Danach hab ich Google gequält und die verschiedensten Seiten zum Problem gefunden, fast alle führten zum Plugin "Dean's Permalinks Migration". Und alle waren super Happy wie einfach und schnell die Lösung funktionierte. Nur leider nicht bei mir.

Wenn ich das Plugin aktiviere und danach ein wget von extern mache, sehe ich in der Konsole, wie Statuscode 301 zurück kommt und korrekt /?p=%post_id%/ in /%category%/%postname%/ umgewandelt und neu angefragt wird. Nur leider erzeugt dies dann einen Statuscode 404.

Selbst neu erstellte Artikel sind nicht erreichbar, die ID wird umgewandelt und der SEO-Name bringt 404.

Hat irgend jemand einen Tipp für mich, was da noch schief läuft?

Viele Grüße und Danke

Talabross