I have discovered that this is exactly what is happening to my site as well, I originally thought that no one could login at all (this only happened to me in IE7 and not Firefox but I had another customer with the same problem in Firefox) and so I turned on Force Cookie Usage....more attempting to troubleshoot led me to find that after a few clicks and losing the zenid login was successful....then led me here through searching LOL
I have the Simple SEO URL's mod installed, is that the same SEO mod you have?
Setting Recreate Sessions to False fixes the problem, but I know despite warnings not to, many ppl paste the links with the zenid so I don't want to set it to False for too long LOL
I will be happy to help try to troubleshoot....if I can LOL :)



