Check AdminCP > Settings > Options > Cookie Settings - what is set for the Cookie Domain? If you allow users to login to your site via both
http://www.yoursite.com and just
http://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.