Porqué llegaste a la conclusión de que session_start() es el causante del problema? Tal vez porque recibes un mensaje de error acerca de que no se pudieron enviar los encabezados porque hubo una salida previa?
Resulta que session_start() sólo envía encabezados para crear/recuperar la cookie donde se almacena el ID de sesión y eso no interfiere en absoluto con otros encabezados.
Entonces, en alguna parte de tu script tienes un espacio, salto de línea o cualquier otro caracter que hace que PHP inicie la salida y cualquier encabezado que pretendas enviar fallará.
Haz que se muestren todos los errores y advertencias de PHP para que puedas determinar dónde se inició la salida y corregir tus scripts., sólo coloca esto al inicio: