Uf, quizás tu problema venga del lado de tu servidor. Averiguá que servidor tenés. Al final de este artículo te da varias opciones para reparar este error dependiendo del mismo.
http://codex.wordpress.org/Using_Permalinks
Acá un artículo de alguien con un problema similar
http://wordp.relatividad.org/informa...-de-wordpress/