Il cookie deve essere il primo output che fai. Se ha fatto echo in precedenza non puoi!

Spesso però il problema é semplicemente un file php che inizia (o finisce) con una riga vuota (prima di <? o dopo ?>)