WordPress keeps logging user in/out

Behavior:

• User logs in successfully
• When user tries to access a portion of the site that can only be viewed by logged-in users, they are told they need to log in.
• When they visit the login page, they are shown that they are in fact already logged in.
• If they return to the protected page, they are asked to log in again.
• Wash, rinse, repeat
• It’s essentially like the site forgets that they’re logged in unless they’re on the actual login page.

Troubleshooting Attempts:

• Disabled all plugins
• Reverted to out-of-the-box TwentyTwelve theme
• Re-installed WordPress 4.2.1
• Ensured that WordPress Address and Site Address in General Settings match exactly

Any guidance would be greatly appreciated!