This is a client side error. Nothing to do with the database. Usually, if the hostname used in tnsnames.ora are not resolvable by the client then the subject lined error appears.
For my case, I was facing this error for a 2 node RAC cluster 11gR2 database. We are using SCAN address in the tnsnames.ora. Even though the client can resolve scan still it's failing.
Because, not only the SCAN but all server in the cluster needs to be resolvable by application clients. This includes the host VIPs and real IP of all the servers in the RAC configuration.
Look at the demonstration of this error:
I can ping the DB alias from client pc.
But, Can't connect to the database using SQLPLUS.
It's because, the client firewall rule is blocking it from communicating either.
VIP/Real IPS of all the servers associated with RAC configuration.
The problem was fixed after fixing firewall in accessing VIP.