Users being logged out constantly

Users are automatically logged out constantly. If they navigate anywhere on the site or click on any internal links, including when trying to message another user. They are logged out and forced to the login page. Often, it doesn’t actually redirect to the login page; instead, the menu link at the top simply changes from “Logout” to “Login.” Any ideas?