No es ningún misterio sin resolver, todo lo contrario es noticia pública resuelta demasiadas veces: No puedes inicializar sesión después de haber tenido algún tipo de salida al navegador. Claramente en la Doc:
www.php.net
Lo que sí sería un "misterio" (no necesariamente sin resolver) es que el problema haya sido al migrar de un hosting gratuito (el cuál generalmente agregan código al inicio de todos los archivos) a uno de pago
sin modificación alguna!!!! ¿?
Quizá en el hosting gratuito estabas desabilitados los mensajes de error... el error estaba pero no lo veías....
Un saludo!