Hi,
Well, the only thing I still can propose is
1) Change all host names with IPs - maybe host name is resolvd wrong
2) Try setting TRACE_LEVEL_CLIENT=16 in SQLNET.ORA. This is going to dump the entire network packages into the trace file and hopefully will help
3) Try connecting to the server, using easy connect ( I assume you use 10g)
That means instead of connect string specify host: port/service
4) Put here the output of lsnrctl status and the fragment of the tnsnames.ora you use

Good Luck