Activas el MOD REWRITE ?
Cita: Options FollowSymLinks
RewriteEngine On
Has probado con algo mas simple o lo has probado en un servidor local (apache instalado en tu pc) ?
Ademas......deberias fijarte que tu hosting este cargando el "modulo de apache" correspondiente (mod_rewrite) mediante PHP_INFO()