How can I disable or fix the cookies must be turned on message?

Members are getting the cookies must be enabled message when they try to logon. In every case we have researched, cookies were enabled and the message was sent in error.

If you resend your login a second time, the login works correctly. Many members have thought our site was down or they were doing something wrong.

Can this error be fixed or the message/blocked login be disabled?