cqlsh giving OperationTimedOut

I have a 3-3 node cassandra cluster on 4-core 16GB Ram EC2 m4.xlarge instances spread across two regions in AWS(US and Singapore, each with replication factor of two with NetworkReplicationStrategy). When I try to connect to it using cqlsh, I get the following error

Connection error: ('Unable to connect to any servers', {'127.0.0.1': OperationTimedOut('errors=Timed out creating connection, last_host=None',)})

I get the same error even if i execute from the node itself or through using teh public ip.

Anyone has also experienced this before? Any suggestions?