How are you checking to see if the cookies are there or not? Checking cookies array doesn't tell you the whole story. If you don't already have it, download the Web Developer Addon for FireFox. It has a feature to view, edit, and delete cookies for the site you are on. View your cookies after logging in. That will give you insight as to what is actually being set by the browser. Then close the browser and open again, visit site, and view the cookies again. See if they are perhaps still there, and just not being read.
I've learned the hard way that it's a really good idea to set the cookie path and domain explicitly rather than letting PHP default it. Otherwise cookies from mydomain.com will have a different path than www.mydomain.com and that can lead to the www cookies not being read from mydomain.com and other fun stuff. We now always explicitly set our cookies, after wasting probably a week's worth of development time over the course of 6 months trying to track that issue down.
If paths aren't the issue you might be inadvertently deleting the cookies. Do the values you are passing in from the SESSION always exist for sure when that code is run? A false value tells PHP to delete a cookie, which could happen by accident if the values are not defined in the array and you don't have a strong error reporting level.