Some of the newer browsers prevent "third-party" cookies from being set, either by default or as an option. That is, if the cookie is coming from somewhere other than where the frameset is hosted, the browser assumes it's an evil spyware cookie and blocks it.

You can probably turn off this protection in your own browser to verify whether this is indeed the problem. If so, you've got a nasty problem, as many users would have to correct their browsers.