Whenever I have trouble with cookies, I usualy check for a few standard problems:
Is the header the first thing you're printing? It must be absolutely the first. A debugging print will mess up the parsing of the headers.
Are the headers being printed in more than one place? Most (all?) header printing routines print a blank line at the end, and that terminates the headers.