... creo un pequeño malentendido con las palabras de Cluster... el caso es que, en todo el código (incluyendo include()'s) no debes tener 
ninguna salida antes de ocupar session_start() y header()... así que, donde comentas: 
Código:
 /*AQUI VA CÓDIGO EN HTML QUE ME IMAGINO NO AFECTARÁ PARA NADA*/
   temo que no es así... si afecta y es el motivo de tu error. 
Ya lo dijo Clus, necesitas reordenar tu código de manera que primero hagas tu validación de manera que no imprimas nada (en pantalla) antes de redireccionar; hasta lógico es si lo piensas bien ¿para qué tener alguna salida si se va a redireccionar?, ¿para qué mostrar HTML si se le va a impedir su acceso??. 
www.php.net/header 
... no sé que hayas editado... pero procura hacerlo solo en casos necesarios. Ve que puedes confundir a quienes intentamos aportar algo de ayuda (yo estoy confundido, no sé si el comentario de PeiShar tenga igual relación). 
Un saludo!