This was mentioned in a comment to another answer, but I wanted to move it to an actual answer since this was also the problem in my case and I would have upvoted it if it had been an answer.
I'm on Linux and the tnsnames.ora file was not set to readable by everyone. After making it readable connecting via tns locally worked.
$ chmod +r tnsnames.ora