Creating mongo 3 node replica set on ec2 problems

Question

I'm trying to create a 3 node cluster of mongo replicas on ec2 instances, with internal ips 10.168.xxx.xxx, 10.166.xxx.xxx and 10.188.xxx.xxx, my config file is:

dbpath = /home/ubuntu/mongo-data/
logpath = /home/ubuntu/mongo-data/mongod.log
logappend = true

journal = true
fork = true
smallfiles = true
pidfilepath = /home/ubuntu/mongo-data/mongod.pid
replSet = appNameReplicaSet

I launched mongod -f mongod.config on each instance, and on one of those I tried:

$ mongo
> rs.initiate();
{
"info2" : "no configuration explicitly specified -- making one",
"me" : "ip-10-168-66-132:27017",
"info" : "Config now saved locally.  Should come online in about a minute.",
"ok" : 1
}
> rs.add('10.166.xxx.xxx:27017');
//after LONG pause
{
"errmsg" : "exception: need most members up to reconfigure, not ok : 10.188.22.254:27017",
"code" : 13144,
"ok" : 0
}

I also tried:

config = {
    _id: 'appNameReplicaSet',
        members: [
        {_id: 0, host: '10.168.xxx.xxx:27017'},
        {_id: 1, host: '10.166.xxx.xxx:27017'},
        {_id: 2, host: '10.188.xxx.xxx:27017'}
    ]
}
rs.reconfig(config, {'force':true})
{ "ok" : 0, "errmsg" : "a replSetReconfig is already in progress" }

.log file:

Sat Jul 27 01:33:59.149 [initandlisten] connection accepted from 127.0.0.1:36931 #4 (1 connection now open)
Sat Jul 27 01:34:02.468 [conn4] replSet replSetInitiate admin command received from client
Sat Jul 27 01:34:02.470 [conn4] replSet info initiate : no configuration specified.  Using a default configuration for the set
Sat Jul 27 01:34:02.470 [conn4] replSet created this configuration for initiation : { _id: "appNameReplicaSet", members: [ { _id: 0, host: "ip-10-168-xxx-xxx:27017" } ] }
Sat Jul 27 01:34:02.470 [conn4] replSet replSetInitiate config object parses ok, 1 members specified
Sat Jul 27 01:34:02.473 [conn4] replSet replSetInitiate all members seem up
Sat Jul 27 01:34:02.473 [conn4] ******
Sat Jul 27 01:34:02.473 [conn4] creating replication oplog of size: 990MB...
Sat Jul 27 01:34:02.474 [FileAllocator] allocating new datafile /home/ubuntu/mongo-data/local.1, filling with zeroes...
Sat Jul 27 01:34:02.485 [FileAllocator] done allocating datafile /home/ubuntu/mongo-data/local.1, size: 511MB,  took 0.01 secs
Sat Jul 27 01:34:02.485 [FileAllocator] allocating new datafile /home/ubuntu/mongo-data/local.2, filling with zeroes...
Sat Jul 27 01:34:02.491 [FileAllocator] done allocating datafile /home/ubuntu/mongo-data/local.2, size: 511MB,  took 0.005 secs
Sat Jul 27 01:34:02.491 [conn4] ******
Sat Jul 27 01:34:02.491 [conn4] replSet info saving a newer config version to local.system.replset
Sat Jul 27 01:34:02.492 [conn4] replSet saveConfigLocally done
Sat Jul 27 01:34:02.492 [conn4] replSet replSetInitiate config now saved locally.  Should come online in about a minute.
Sat Jul 27 01:34:08.435 [rsStart] replSet I am ip-10-168-xxx-xxx:27017
Sat Jul 27 01:34:08.435 [rsStart] replSet STARTUP2
Sat Jul 27 01:34:09.441 [rsSync] replSet SECONDARY
Sat Jul 27 01:34:09.441 [rsMgr] replSet info electSelf 0
Sat Jul 27 01:34:10.440 [rsMgr] replSet PRIMARY
Sat Jul 27 01:34:26.513 [conn4] replSet replSetReconfig config object parses ok, 2 members specified
Sat Jul 27 01:37:45.835 [conn4] couldn't connect to 10.188.xxx.xxx:27017: couldn't connect to server 10.188.xxx.xxx:27017

UPDATE: added output of rs.initiate() & logs;