Users can't log in sometimes Drupal 7.5, PHP 5.6.27 Debian 8, remote host.

We are running into a problem where some people can't log in some of the time and sometimes it works if they try multiple times. Users have reported the issue with different browsers and only a small percentage of people seem to be affected. Please note that I can only reproduce the error on occasion, and very inconsistently.  

Watchdog simply shows that a session is opened for the user, even if the front page shows that they are not logged in.

Edit: Users can usually log in if they enter the wrong password first!

Things I've tried:


changed cookie_domain from www. to .
made sure rewrite condition allows https
cleared Drupal cache
we have no external caching
added redirect from port 80 only to default-ssl.conf
Users can't always log in with a one-time log in link generated with drush uli "[username] (the site will ask them to log in)
creating a custom login module to set a new custom session suggested here
added some cookie configurations to the sites/default/settings.php file as suggested in this post
installed the website on a different environment with PHP 5.5 and different settings.php .htaccess and php and mysql configurations.


Known Workarounds:
May or may not provide clues.


Sometimes if we change a user's password, they can get in that way
If a user enters the wrong password first on purpose then logs in, they are able to log in
Sometimes we can provide a one-time log in link for users to get in, but that doesn't always work


Edit: I've managed to recreate the issue on a local development environment with different settings files. I removed all the settings files information from my original post since I know now that they are not relevant.
That can happen if the site is redirecting to a different domain or to a secure/non-secure protocol upon login. I.e. with/without www or to http/https. If so, you could set a base domain and cookie domain in settings.php, and/or enable www/non-www redirect in .htaccess.

It also seems there may be a problem with PHP 5.6.1.
https://www.drupal.org/node/2723927
https://www.drupal.org/node/2379019