My organization is in the process of implementing single sign-on for web based applications using an authentication server with cookies. We haven't yet run into these problems.

Are your certificates issued by a well know CA, such as Verisign? Which versions of Netscape encounter the redirect warning?