Well I have the similar issue on my local(intranet) wp dev multisite site.
One good thing is that superadmin user DOES NOT have this issue, I can always login as superadmin, but no other user can login to its site!
Have tried all above mentioned methods, but no use!. My wp-admin/ permissions ARE 0644.
