No consigo cambiar la estructura de los permalinks

Buenas a todos!
Mi problema es elsiguiente: He decidido cambiar la estructura de los permalinks de mi blog, desde su forma actual por defecto (tipo: http://www.myblog.com/?p=123) a la estructura ‘http://www.myblog.com/sample-post/’. He intentado diversos métodos para hacerlo, sin resultado:

-Directamente, desde la página ‘permalinks’ en ‘Ajustes’
-Lo anterior, más alguna modificación en el htc.access que he encontrado googleando por allí. Sin consecuencias catastróficas,por lo menos.
-Todo lo anterior, más usando algún plug-in para hacer una redirección 301.

Y nada. Sistemáticamente, una vez efectuados los cambios correspondientes obtengo errores 404 al acceder a todas y cada una de las páginas (post y categorias. Sí accedo a la home, claro).

En fin… casi, casi he tirado la toalla, porque ya he dedicado a este tema muchas horas. Es evidente que estoy metiendo la pata en algo, pero ya no sé por donde tirar!

Agradeceré enormemente cualquier ayuda o sugerencia para solucionarlo.

Gracias por anticipado!