Se hai pozioni di codice scritte in questo modo
Codice PHP:
<?php
  
//codice
?>
<?php
  
// qui il redirect
?>
invii senza accorgertene degli 'a capo'. Discorso simile può esser fatto per spaziature e tabulazioni.

Se sei sicuro al mille x mille di non inviare alcun carattere di output prima del redirect, verifica che la codifica del file non sia UTF8+BOM.

Il carattere BOM (che ad esempio mette blocco notes quando salvi in utf8) viene inviato prima dell'header e può causare il problema che hai riscontrato.