Calling rs.initiate() (i.e. without a configuration object) will cause MongoDB to create its own replicaSet configuration. Unfortunately, for "host" it chooses the computer name without the domain name. Of course this is only a problem when working with computers across different domains, which is probably why no one has noticed it before now.

Workaround: call rs.initiate with a configuration object like this:

    {
        _id: "rs0",
        members: [{
            _id: 0,
            host: "host.domain.tld:port"
        }]
    }