Lotus Notes replication is using port 1352 so it needs to be opened on both servers you plan to replicate.
The easiest way to check is to telnet the server on this port. IE:
telnet IP/SERVER_NAME 1352
If connection succeeds, you then need to create the proper replication document from Lotus Domino Administrator.