Java OracleDB connection taking too long the first time

I'm having a problem when connecting to an Oracle database, it takes a long time (about ~5 minutes) and it sends the below shown exception. Most of the time, after the first error, the next connections for the same process work correctly.

It is a RHEL 6 machine, with two different network interfaces and ip addresses.

NOTE: I am not using an url like: "jdbc:oracle:thin:@xxxx:yyy, it is actually: "jdbc:oracle:thin:@xxxx:yyyy:zzz. The SID is not missing, sorry for that :(

This is roughly what I've isolated:

bin/java -classpath ojdbc6_g.jar -Djavax.net.debug=all -Djava.util.logging.config.file=logging.properties

Class.forName ("oracle.jdbc.OracleDriver")
DriverManager.getConnection("jdbc:oracle:thin:@xxxx:yyyy", "aaaa", "bbbb")

Error StackTrace:

java.sql.SQLRecoverableException: IO Error: Connection reset
        at oracle.jdbc.driver.T4CConnection.logon(T4CConnection.java:533)
        at oracle.jdbc.driver.PhysicalConnection.<init>(PhysicalConnection.java:557)
        at oracle.jdbc.driver.T4CConnection.<init>(T4CConnection.java:233)
        at oracle.jdbc.driver.T4CDriverExtension.getConnection(T4CDriverExtension.java:29)
        at oracle.jdbc.driver.OracleDriver.connect(OracleDriver.java:556)
        at java.sql.DriverManager.getConnection(DriverManager.java:579)
        at java.sql.DriverManager.getConnection(DriverManager.java:221)
        at test.jdbc.Main(Test.java:120)
Caused by: java.net.SocketException: Connection reset
        at java.net.SocketOutputStream.socketWrite(SocketOutputStream.java:113)
        at java.net.SocketOutputStream.write(SocketOutputStream.java:153)
        at oracle.net.ns.DataPacket.send(DataPacket.java:248)
        at oracle.net.ns.NetOutputStream.flush(NetOutputStream.java:227)
        at oracle.net.ns.NetInputStream.getNextPacket(NetInputStream.java:309)
        at oracle.net.ns.NetInputStream.read(NetInpu