I ran into the same problem using CGI.pm's cookie tricks. Here's what I discovered it (as I remember it):
I was setting and retrieving the cookie correctly, the problem was that the cookie hadn't appeared in the environment before I tried to retrieve it, because the page that followed the redirect hadn't had it's headers sent yet, which contained the cookie.
I saw a good solution to this in Justin Simoni's code (which I haven't tested yet.). He used the CGI.pm 'redirect' function, which can include attributes for both 'location' and 'cookie'.
Before I found that, I was using a cheesy hack of printing a page with a meta tag refresh instead of redirecting directly. This insured that the cookie appeared in the environment before I tried to retrieve it again.
Good luck! -mark