For all who are still following, I have yet to track this down. However, I am onto a new clue:
1) User changes their password
2) User attempts to log in: They are successful for a moment, but immediately logged out again (usually by the first XHR request, which returns 401 unauthenticated)
3) If I restart the server (heroku restart), User can log in with the new password and remain logged in as expected
What would restarting the server do exactly regarding sessions that would "fix" this problem? I think, one thing, perhaps, this may have to do with the fact that I'm running Rails on the puma web server, multi-threaded. Subsequent requests *sometimes* work, and *sometimes* don't.
As a test, I changed my puma thread (on my staging server) to run 1 worker and 1 thread only. Sure enough, actually, it seems that my problem goes away!!!
So... now what do I do to fix this in production? I can't make it a single-thread, that would defeat the purpose of doing threadsafe rails 4 with puma....