Debes modificar los permalinks como dices, pero asegurate de tener el .htaccess con permisos de escritura para que WP pueda editarlo... sino WP muestra los links como /%postname%/ pero el server no los "transforma" correctamente y por eso da error.
Suerte!
