Replication apparently has different DNS requirements than Management Studio. I added remoteserver.na.mycompany.com as a cname to remoteserver.eu.mycompany.com and then everything started working fine. Before adding the DNS entry I was able to connect just by the first part of the server name, but replication couldn't.