I have on user on my site who the cookies do not work for. I have the cookies before the header of the script. His IE security level is set to Allow all cookies. He's tried to change the time and delete all cookies and Temporary internet files.
They could also have a program on their computer that is screwing with the cookies. I had a friend that was the only person who couldn't get on my site, cause the cookies were all screwed up. She uninstalled one of her stupid security softwares, and bam! no more cookie problem.