Vaya es un servidor windows :D este problema es bastante comun o al menos lo fue para mi al trabajar con actionhosting
carga en tu servidor un archivo llamado info.php y como contenido le pones
visita esa url en tu navegador y revisa que este activo el modulo mod_rewrite
sin este nunca te funcionaran los permalinks amigables.