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.