This looks alright, but it might get a bit messy when you're creating circular references. I think it might be easier to use some kind of "table" to initialize the objects from:

my %rooms = (
   townsquare => { 
      name => 'Town Square'
      east => 'store',
   },
   store => {
      name => 'Town Store',
      west => 'townsquare',
   }
);
my %room = ();
# create rooms without connections
while (my ($id,$roominfo) = each %rooms) {
   $room{$id} = Room->new($roominfo->{name}); 
}

# since we now already have all room objects,
# it's easier to add connections to them
while (my ($id, $roominfo) = each %rooms) {
   for (qw(east west north south)) {
     $room{$id}->"add$_"($room{$roominfo->{$_}});
  }
}
[download]

Ofcourse, you could also store just the roomid for connections in the room objects and look them up in the hash when the exitX() methods are called.