¿Qué parte de "la llamada a session_start() debe ser en la primera linea" no has entendido aún?
Entiende que esto que haces está mal:
Antes de llamar dicha función ya hay HTML y eso arruina todo.
Por favor, vuelve a leer el manual hasta que lo comprendas.