Eso es porque
header() tiene que ser llamado antes de enviar cualquier tipo de texto a la pantalla.
Osea, esto estaria errado:
Código PHP:
<html>
<?php
header("Location: inicio.php");
?>
Esto estaria correcto:
Código PHP:
<?php
header("Location: inicio.php");
?>
<html>
Editado: Nose porque estaba pensando en header(), cuando tu pregunta es por session_start() :) pero igual mi respuesta aplica.