Redirection Consistency
I have seen similar behaviour when the website is not being redirected consistently.
In Joomla 3.x, you probably shouldn't be using the livesite parameter in the configuration.php file but if you are, make sure it's consistent with any redirections in your .htaccess file or anywhere else. For example, if you are redirecting the non-www version of the website to the www version of the website, make sure the livesite parameter (if you are using it) is set to the www version of the website.
.htaccess
Back up your .htaccess file and temporarily copy the contents of htaccess.txt to .htaccess to reset your .htaccess file back to defaults to see if something in .htaccess is causing the issue.
Joomla Update and Check for Malware
You should also upgrade to the latest version of Joomla as Joomla 3.4.1 has some known vulnerabilities. I'd be inclined to scan the website using myjoomla.com or similar in case the website has been compromised and this is the reason you are having intermittent login issues.
Third Party Extensions
What third party extensions are enabled on the website? Try temporarily disabling these one by one to check if a third party extension is responsible. Try updating all third party extensions to the latest versions as this may also help fix the issue.
Session Table
The [prefix]_session table is frequently updated in Joomla and can occasionally become corrupt. Run a repair on the table using phpMyAdmin or Akeeba Admin Tools or similar.
Front-end / Back-end
Are the back-end and front-end logins both affected or only one of these? This information may help narrow down the issue.