A lo que tu te refieres es a los ajustes internos en el panel de administración de Worpdress.
La cuestión es ?p=123 hace referencia al post con ID en la base de datos 123. Al cambiar el mismo a %postname% estás utilizando el slug que normalmente suele ser el titulo sin espacio y con guiones, por ejemplo, titulo-de-mi-entrada, entonces lo que hace es buscar dicho slug en la base de datos. Si le dices que el slug es 123, Wordpress va a ir a buscar un post con el título/slug 123, pero como es lógico, no existe.
¿Donde está la solución? Tienes que crear un proceso intermedio que busque en la base de datos de forma automática el slug del ID 123, y que te lo redireccione al slug, o sea, /titulo-de-la-entrada.
---------- Post agregado el 05-may-2014 hora: 16:39 ----------
Un momento porque me da que estamos hablando de cosas diferentes. En realidad ?p=123 si se resuelve. En el caso de que el problema te los de %postname% puede ser problema del .htaccess, que posiblemente no se esté añadiendo la nueva configuración que le asignas.
Cuando estableces el %postname% Wordpress te avisa en el caso de que no pueda escribir en el .htaccess, poniéndote un código que debes copiar y pegar.