Si realmente ese es el problema debes hablar con tu hosting, ya que es importante que te presten soporte completo para soportar Wordpress sino no vas a tener ese problema sino muchos otros.
Si no te dan soporte para Wordpress tendrías que moverte a otro hosting.
La otra posibilidad es que el archivo .htaccess esté bloqueado, quizás con permisos erróneos (o de seguridad - algunos plugins de seguridad son un poco raritos).
En ese caso bastaría con ingresar por medio de FTP, eliminar el archivo htaccess y desde el adminsitrador de Wordpress volver a guardar la nueva configuración de enlaces permanentes para que se genere un nuevo archivo, es un excelente truco cuando ocurren problemas con el archivo htaccess (que por supuesto aprendí en Forobeta, jejejeee).