Ese error es muy común, cuando envías salidas en pantalla antes de la función header, o tenes espacios en blanco antes de <?php.
http://www.php.net/manual/es/function.header.php
lo dice el manual, fijate que está pasando en tu código, a ver si envias algo a mostrar en pantalla antes del header