Rite your problem is quite simple. This one catches out a lot of people.
The header finction outputs an HTTP header string to the browser for a command such as location redirecting.
But this output must occur before any other data is sent to the browser including html tags, spaces in your php script (even if you put one space at the top of the script)or a \n command. Check your scripts for these commands and take out any info that is being sent to the browser.
Also make sure that you are not running out of a include script.
I hope that helps you.