I'm having the same trouble. Windows Vista SP1, IE8.
The suggested solution above is incorrect and does not solve the problem. By selecting the Internet Explorer options, I would expect CCleaner to remove all. If CCleaner offers to never delete certain objects, I would also expect CCleaner to always preserve them.
Of course, unticking all options prevents CCleaner from removing the cookies I want to keep, but also leaves all other cookies at the same time. In other words, it's not solving the problem but merely telling the program to forget about cleaning certain aspects.