Mongodb rs.add() new member in STARTUP state
I figured out what is wrong with my replica set clusters. You need to provide an argument to rs.initiate(), which is the configuration document. If you don't specify the document, it will read the configuration from the /etc/mongod.conf which will has no configuration whatsoever for the replica set. The configuration for rs.initiate() looks something like this:

rs.initiate(
   {
      _id: "myReplSet",
      version: 1,
      members: [
         { _id: 0, host : "mongodb0.example.net:27017" },
         { _id: 1, host : "mongodb1.example.net:27017" },
         { _id: 2, host : "mongodb2.example.net:27017" }
      ]
   }
)

But if you do not know before hand how many replica sets you want to add to the cluster it is ok, just specify the first one and the subsequent ones will be added without any problems:

rs.initiate(
   {
      _id: "myReplSet",
      version: 1,
      members: [
         { _id: 0, host : "mongodb0.example.net:27017" }
      ]
   }
)