NextGen Gallery y enlaces permanentes personalizados

Hola, estoy instalando para uno de los sitios web en el que estoy trabajando el NextGenGallery, añado una galería en una de las entradas, tras publicar la entrada hago la prueba para ver si se visualiza correctamente y cual es mi sorpresa que al entrar el la entrada recién publicada me sale la pagina que tengo de error 404 en mi plantilla, lo raro viene que si pongo los enlace permanentes en modo predeterminado en vez de en modo nombre de entrada funciona correctamente. Mi pregunta es:

¿A qué se puede deber este problema? ¿Cómo puedo solucionarlos? A la persona a la cual le estoy realizando la web quiere usar url personalizadas por el el tema del SEO.