I figure it couldn't hurt to try and find users who're having the issue (or try to replicate it) and drop the "remember me" time frame down to say a month...
Think about it, it "works" for them when they don't mark "remember me", so it kind of makes sense that it could be the issue...