Posta il contenuto di .htaccess.

Prova così:

<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteRule ^index\.php$ - 
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php 
</IfModule>

Hai per caso installato "Top Level Categories" o plugin simili?
Prova quanto si dice qui: wmaster.it/wordpress/problema-permalink-wordpress

Le modifiche al core di Wordpress sono da evitare, soprattutto perchè vanno perse in seguito ad aggiornamento. prova invece ad inserire questo codice nel file functions.php del tuo tema e ad attivare i permalink con la struttura che preferisci:
[php]remove_filter('template_redirect', 'redirect_canonical');
[/php]

Anche io mi ritrovo con lo stesso problema, i permessi di scrittura sono tutti abilitati ma niente da fare

Ciao,

che versione hai di WP? è un problema che si è verificato in seguito ad un aggiornamento? hai plugin che riscrivono le url installati?
Ciao

p.s. dimenticavo, in impostazioni/generale nei campi Indirizzo WordPress (URL) e Indirizzo del sito (URL) hai qualcosa del tipo http w ww.nomesito.ext?

Ultima versione, nessun plugin che riscrive URL, l'installazione è recente.

Per il PS no, ho solo il link del sito come è giusto che sia.

Con /%postname%/ non funziona mentre con index.php/%postname%/ invece non crea problemi.

Riporta la struttura dei permalink allo stato originale (default) e salva le modifiche. Esci da wp e cancella il file .htaccess (fai una copia in locale prima).
Apri il db mysql, fai un backup, e poi vai in wp_options; troverai rewrite_rules: elimina questa voce. Controlla se il sito funziona, se va prova a modificare la struttura dei permalink e vedi se va. Fammi sapere.

Non c'è la voce rewrite_rules O_o

Ho un VPS

Non serve a niente cancellare le rewrite_rules da wp_options. L'operazione è eseguita in automatico, ogni volta che si entra nella impostazioni relative ai permalink.