I've seen this before, but it's been a long time. I remember creating a test page to dump out the cookies for the site and they'd change on every refresh. I don't remember if we ever found a solution. I want to say that the issue cleared up after another update from Microsoft, but it was so long ago I honestly don't remember.
What's happening is you're getting new values for the CFID and/or CFTOKEN cookies that CF creates and uses to keep track of the browser's state. (The web is by its nature stateless, but that's not very helpful when you need to do transactions.)
Here are some of the possible issues I've seen other people mention:
- Inconsistently using www.domain.com and domain.com. The site may work either way, but unless you're using domain cookies the cookies will care
- Privacy settings in IE being too restrictive
- Special characters in the domain name (underscore is mentioned specifically)
- Lack of P3P policy on the web server (back to the privacy settings)
As for solutions, have you tried using J2EE session variables? Some people have had success with those in solving this.