You definitely do not have your cookie domain set up correctly.
Since you allow users to login to your site via both
http://www.yoursite.com and just yoursite.com, then you MUST have your cookie domain (AdminCP > Settings > Options > Cookies and HTTP Header Options > Cookie Domain) set to ".yoursite.com" (no quotes, but note the period at the beginning) or your users will have problems.