In my experience, replica sets work best when they have DNS names that both the clients and the servers can resolve.
I have used both pymongo and php MongoClient, and if the client machine uses the IP Addresses of the replica set, but the replica set was setup using DNS names, the client will fail to connect (probably because when asking the replica set which node is the primary, the replica set probably returns the DNS name).
If I use DNS names (I just modify the hosts file on the client) then the connections do not fail.
From the documentation on replica sets:
Each member of the replica set must be accessible by way of resolvable DNS or hostnames
Hope this helps you debug your issue.