Instead of trying to determine who got connected first, why don't you just have all the players pick a random number using arc4random ?
int randomNumber = arc4random%1000000;
The player with the biggest number can play first. You will have to make sure all the players send each other their random numbers so everyone can compare and decide who is first. In the above example, the range would be upto 1 million, so the odds of two players picking the same random number is low.
If two players do pick the same random number, you could compute the hash of their playerId's, and have the player with the larger hash be first.
if ([GKLocalPlayer localPlayer].playerID.hash > otherPlayerId.hash )
The chances of a hash collision occurring are very low, since the playerId strings are short. You can still check for this collision and handle it appropriately (maybe by hashing again ;) ).