Este é um serviço de utilidade publica para a comunidade wordpress e até esta presente dentro da pagina de suporte em portugues
mais os argumentos não são bem claros

Me deparei que este problema quando instalei a versão wordpress 3.2 português

Como de costume básico fui alterar os amigos SEO ” Permilinks ” para o estilo que gosto em minhas paginas

Apenas : sedominio.com/nome-do-post

O que seria basicamente escolher a opção estrutura personalizada

e inserir a opção /%postname%/ e pronto já é para funcionar normal

Só que isto não acontece de forma simples nesta versão do wordpress 3.2

O básico para saber se este é seu problema é o seguinte se você já costuma hospedar e instalar versão do wordpress e sempre funcionou direitinho os permalinks ( no meu caso foi isso ) então o problema deve esta mesmo na versão do wordpress caso contrario se for em um novo servidor você deverá saber se as funções mod_rewrite e FollowSymLinks de sua hospedagem esta habilitadas , além disso veja se o wordpress gerou um arquivos .htacess

Não vou me atentar aos detalhes vamos partir de que esta tudo ok com seu servidor de hospedagem e que apenas o permalinks esta falhando não e não encontra a página criada dentro do wordpress

Segue a copia fiel do suporte wordpress

• Abra o arquivo wp-includes/vars.php usando o editor do WordPress , dreamweaver ou blog de notas
• Procure por

  $is_apache = strstr($_SERVER['SERVER_SOFTWARE'], 'Apache') ? 1 : 0;

  and replace it with

  // $is_apache = strstr($_SERVER['SERVER_SOFTWARE'], 'Apache') ? 1 : 0;

• Adicione uma linha nova após

  // $is_apache = strstr($_SERVER['SERVER_SOFTWARE'], 'Apache') ? 1 : 0;

  e digite

  $is_apache = 1;

Depois é só salvar ou atualizar atraves de um ftp

Segue a dica de um plugin para checar se todos os modos de paginas amigáveis esta habilitados de forma corretamente

Procure por  WordPress RewriteRules Viewer

 

Para mim funcionou da seguinte forma apenas deixei como comentário a linha salvei atualizei e pronto

// $is_apache = strstr($_SERVER['SERVER_SOFTWARE'], 'Apache') ? 1 : 0;