As I said earlier, I haven't tried it, so I cannot offer any guarantees ... but that is a bit strange. Are you redirecting within the same domain as your cookie? Can you show the code you are using to determine if the cookie is set in the destination script?

Is it essential that you set the cookies on the first page ... if not, it might be the path of least resistance to set them on the destination page ... ?