If you're in a workgroup instead of a domain... there's one possibility that I can think of.  The administrator account you're using is a local machine account, I'm assuming.  If you're using a local account, it really won't be able to talk to the other machine.

I'm in a domain, and using an account with admin rights for my replication jobs.  Maybe you should try something like using mixed mode security and using a sql server account with system administrator rights for the replication threads (and have the account on both sql servers).