Do you have a custom cookie prefix set? If no, i'd recommend setting one (for security) which will invalidate everyone's login cookie and will force new ones once they log back in.
Another option if you don't want to use a cookie prefix, would be to have users experiencing this error go to the "Cookies" section of the "My Stuff" panel and clear their cookies from there.