If the cookie sets to www, makes sure they always access the site by going to www. This is a problem with my users every now and then.
If they're using Firefox, it might be clearing their cookies on program exit. Have them make sure this setting "Always clear my private data..." is not on, or at least not set to clear cookies.
