Sounds like TRUST between domains are not properly authenticated, what are privileges and kind of account used to start SQL Services on both the machines.
Also check whether subscriber is enabled as a subscriber or chances of not impersonating the sql server agent account.
To do so In EM go to Tools | Replication |Configure Publishers, subscribers, and distributors, select the subscribers tab, ensure the check box beside your subscriber is enabled, and then click on the three ellipses beside your server. Ensure that the impersonate option is selected.
May i dare adding my suggestion, i had the same problem. I had to setup replication b/w two different domains over the internet. The domains didn't have trust-relationship. I tried connecting the subscriber through SA and windows-users, same problem u mentioned.
I squared it away by doing this:
Made a user SQLREP (member of domain-users group) in both domains. Added the user into the local-administrator groups of both the servers(publisher and subscriber).
Checked "THE ACCOUNT IS TRUSTED FOR DELEGATION" option in the "Account-Properties" of this user at both Domain-Controllers. Note: the password for this user must be same at both ends.
SQLREP is the startup-service agent account for both the servers.
Subscriber connects to the other domain through VPN.
With this option; it allows the SQLREP user to be validated on both domains and i can access the systems(over the internet through VPN) only through this user. If i change the password of the user at any side, replication fails.
Obviously if ur domains or on LAN, exclude the VPN setup.
May be i am re-inventing the wheel!! Satya has already mentioned.