Molti utilizzatori hanno lamentato error 404 dopo l'aggiornamento a WP 2.6 clikkando sui permalink.
In tutti i casi il problema nasce dalla presenza di index.php nei permalink.
Il bug verrà risolto con le prossime versioni.
Soluzioni:
Se stai usando Linux/apache in realtà non ti serve avere index.php perchè è stato pensato per le installazioni su server windows/IIS, togliendolo il problema si risolve.
Il problema si risolve anche rimettendo i permalinks standard.
Un altra soluzione è quella di aggiungere qualcosa nei campi tag e categoria, "tag" e "categoria" vanno benissimo.