Permalinks auf Standard zurücksetzen. Inhalt der .htaccess löschen und diese anschließend per CHMOD beschreibbar machen (777). Dann ins Backend gehen und die gewünschte Permalinkeinstellung auswählen und speichern. Anschließend die Schreibrechte der htaccess wieder zurücksetzen (644).
Beachte: Wenn Du WP nach diesem FAQ Artikel eingerichtet hast, dann liegt die htaccess nicht im gleichen Verzeichnis wie die wp-config.php, sondern eine Ebene höher.
Zudem wäre zu klären, ob der Server mod_rewrite unterstützt. Frage hierzu beim Hoster nach oder wirf mal einen Blick in die PHPInfo. Wenn nicht, wird's auch erstmal nichts mit den Permalinks... Es gibt (glaube ich) Pluginlösungen für die Verwendung von Permalinks ohne mod_rewrite.