Il suffit d'aller dans wordpress /wp-admin, qui fonctionnera toujours, et de naviguer dans settings->permalinks. Lorsque vous vous rendrez sur cette page, wordpress reconstruira votre fichier .htaccess et tout fonctionnera à nouveau.
EDIT (DE http://codex.wordpress.org/Using_Permalinks )
Si ce qui précède ne fonctionne pas :
La navigation par page ne fonctionne pas
Parfois, la navigation vers la deuxième page (et les pages suivantes) des articles ne fonctionne pas comme prévu.
Le résultat d'un clic sur un de ces liens est que la page se charge avec tout l'environnement (en-tête, pied de page, barre latérale), mais au lieu d'une page de messages, il y a un message d'erreur : "Désolé, aucun message ne correspond à ce critère".
Cela est dû à un problème dans le fichier .htaccess que WordPress génère. Pour résoudre ce problème, supprimez le contenu de votre fichier .htaccess et recréez-le.
Dans le Panneau de configuration, allez dans Gérer > Fichiers (Plus d'informations sur la modification des fichiers).
Cliquez sur le lien vers votre fichier .htaccess pour en modifier le contenu.
Copiez le contenu du fichier et collez-le dans un fichier texte dans un éditeur de texte. Il s'agit d'une précaution au cas où votre fichier .htaccess contiendrait des entrées manuelles pour des redirections, des refus ou d'autres astuces htaccess pratiques.
Supprimez tout le contenu de votre fichier .htaccess et cliquez sur le bouton Mettre à jour le fichier.
Dans le Panneau de configuration, allez dans Options > Permaliens.
Cliquez sur le bouton "Update Permalink Structure" pour générer de nouvelles règles de réécriture pour vos permaliens.
Testez les résultats en utilisant un lien qui avait été rompu auparavant.
Réintroduisez toutes les entrées htaccess manuelles dans votre fichier (placez les entrées htaccess manuelles avant la balise #
BEGIN WordPress ou après # END WordPress lignes).
Vous pouvez également effectuer des étapes similaires en supprimant les fichiers .htaccess du serveur, en créant un nouveau fichier .htaccess vide, en modifiant ses permissions à 666, puis dans Options -> Permalinks générer un nouvel ensemble de règles htaccess en cliquant sur le bouton Update Permalinks Structure.
Si cela ne fonctionne toujours pas, jetez un coup d'œil aux forums d'aide de WordPress, en particulier à http://wordpress.org/support/topic/permalink-nextpage-doesnt-work#post-283222