Bien, no me estrañe que falle. Estas mandando todo ese HTML a la salida. Quita todo el HTML de delante del session_start(). Antes del header() y de mandar la informacion de cookies no debes enviar ninguna salida al navegador. Ni HTML, ni textos, ni espacios, nada.
Claro, ahora me preguntaras por que te funcionaba perfectamente en windows. Si has leido la explicacion que he dado antes, no comento nada de las sesiones; solo header() y cookies. Pero las sesiones tienen dos metodos de propagarse: por URL y por cookies. En el caso que te da error, te dice algo de cookies, por lo que creo que se propaga por cookies y por eso da el error. El metodo de propagacion se puede configurar por php.ini.
Otra razon por la que te podia funcionar perfectamente en windows es si tienes PHP configurado para que alamacene en un buffer toda la salida y la envie toda junta (
http://www.php.net/manual/en/ref.outcontrol.php). En este caso, si se pueden enviar headers() y cookies, porque realmente no se ha enviado nada al navegador, sino que todavia esta en el buffer.
Revisa estas configuraciones, aunque yo te recomendaria quitar ese HTML de ahi delante y ponerlo despues.
Saludos.