If you are using the Oracle instant client, make sure LD_LIBRARY_PATH is set, otherwise, make sure ORACLE_HOME is set.

If the database is on the same box and you are not connecting through a listener, make sure ORACLE_SID is set (not the case for you). If you are connecting using an Oracle listener (which is your case as the database is on another box), make sure TNS_ADMIN is set.

Update
TNS_ADMIN should point to your connectivity file(s) -- tnsnames.ora (tnsnav.ora, sqlnet.ora, protocol.ora)