The most common cause is something causing output to be sent (even if it's just a blank line or space) before the header() call. It should throw an error if that's the case, so you might want to turn on all error reporting to find out. Just add the following either at the start of your script or at least before the the header() call:
ini_set('display_errors', 1); // change to 0 for production version
error_reporting(E_ALL);