estas seguro que tienes modRewrite instalado, habilitado y funcionando en tu instalacion?
lo normal en muchos hostings es que este instalado pero no habilitado.
para chequear si lo tienes habilitado puedes usar este tutorial.
Código:
http://www.wallpaperama.com/forums/how-to-test-check-if-mod-rewrite-is-enabled-t40.html
si lo tienes habilitado, pregunta en la seccion de wordpress del foro :P
si no lo tienes habilitado es muy simple hacerlo.
Código:
http://enarion.net/web/apache/htaccess/mod_rewrite-on-suse/
Espero que sirva todo esto, si no resulta me envias un PM y lo vemos.