I got exactly the same problem as your on one of my users machine. They installed some other application which creates another TNS name some have changes the existing. So next, time when ever I try to connect, it gives the same error. After playing around, I had to do clean reinstall of Client. Then it fixed the problem.

I suggest the same for you.