Bueno, lo primero que te recomendaria seria que subieras un archivo con el nombre phpinfo.php y con el siguiente contenido:
Después intenta ejecutarlo (obviamente accediendo desde tu navegador >.<), en el resultado que arroje, busca la linea que diga "Server API" (sin las comillas) y ve si dice CGI, si no dice CGI y dice algo como Apache, Apache + versión o Apache Handler, si dice CGI es el problema que te explique en mi post anterior, ahora si confirmamos que tu PHP esta corriendo como CGI es muy difícil que el hosting te lo cambie, porque esto implicaria cambiar la instalación de PHP y Apache, posiblemente si es un hosting de paga te puedan dar otra solución, si es un hosting gratuito olvidalo, mejor ve buscando otro
Aquí encontrarás mas información