I'm encountering a problem similar to PHP-651 - I'm connecting to a replica set using the PHP MongoDB driver and under some conditions connecting always takes ~2 seconds, under some it always takes ~1 second and under some it's near-instant.
There's a difference, though - in my case, all servers in the replica set are online and healthy at the time all of this happens in a consistent and reproducible way.

I see that PHP-651 was closed as a duplicate of PHP-686, which in turn was closed with a note by jmikola@gmail.com: "If the issue persists (please attempt to reproduce with the latest 1.5.x release of the driver), please open a new ticket describing the situation."

In my case, the problem occurs with the currently latest driver version: 1.5.5

On to the actual issue itself:

I ordered a MongoDB deployment at Compose (formerly MongoHQ). They provide a replica set URI like this:
mongodb://<user>:<password>@candidate.36.mongolayer.com:10124,candidate.37.mongolayer.com:10124/<dbname>

According to the PHP Mongo driver documentation, I also appended ?replicaSet=<replica-set-name> to the URI.

But when I put all that together, it took 1.7 - 1.9 seconds on each MongoClient constructor call. It did not matter whether I did it in a standalone script executed via CLI or in a web server using Nginx + FastCGI which, as I understand, should manage pool of connections.

So I started experimenting with different URI variations and measuring the average request time.

Ordered from fastest to slowest:

Only primary host, no replica set name
mongodb://...:...@candidate.36.mongolayer.com:10124
Time: 0.1 - 0.2 seconds

Primary host, with replica set name
mongodb://...:...@candidate.36.mongolayer.com:10124/...?replicaSet=...
Time: 0.9 - 1.0 seconds

Primary and secondary host, with replica set name
mongodb://...:...@candidate.36.mongolayer.com:10124,candidate.37.mongolayer.com:10124/...?replicaSet=...
Time: 1.7 - 1.9 seconds

Primary and two secondary hosts, with replica set name
mongodb://...:...@candidate.36.mongolayer.com:10124,candidate.37.mongolayer.com:10124,temple.28.mongolayer.com:10224/...?replicaSet=...
Time: 2.5 - 3.2 seconds

And just for fun:

Primary and secondary, without replica set name
mongodb://...:...@candidate.36.mongolayer.com:10124,candidate.37.mongolayer.com:10124
Gives understandably an error: "candidate.37.mongolayer.com:10124: not master and slaveOk=false"

While the other reported issues concerned replica member sets being down, the Compose admin UI shows that everything is ok and all members of the replica set are healthy.

rs.status() from both 36 and 37 is reporting consistent data. If needed, I can provide the full output, but to summarize:
PRIMARY: c124.candidate.36.mongolayer.com:10124, health: 1
SECONDARY: c124.candidate.37.mongolayer.com:10124, health: 1, syncing to c124.candidate.36.mongolayer.com:10124 (the primary)
SECONDARY: c224.temple.28.mongolayer.com:10224, health: 1, syncing to c124.candidate.36.mongolayer.com:10124 (the primary)
ARBITER: c61.hatch.16.mongolayer.com:10061, health: 1

At the moment, my workaround is to connect only to the primary, without using the replica set name, because it's the only option that doesn't introduce major delays on every request.

But as an article in the Compose blog notes:

"Rule #1: Always Provide Your Driver with as Many Replica Set Members as Possible

Many applications only connect to a single host on startup. This is bad"