Can't connect to service from a different computer

Question

I wrote a service and self-hosted it in a WinForm Application. I also wrote a client WinForm Application to connect to it.
When I tested both applications on my computer they worked just fine. The problem began when I gave my partner the client exe and told him to connect to my computer.
The application through different security exceptions as I tried different computers:

•  token was faulted
•  could not authenticate

Finally we found two computers that could communicate when 1 is the server & the other is the client but not the other way around!
We can't find any security differences between those two.
all of the computers we tried are windows xp, sp2 or sp3. no domain.
At a point I opened the VS2008 default service and wrote the most simple client I could think of. This application bahaved like mine. I did not tuch any default service configuration that the editor create.
I also tried to set security to "None", but after the client.Open() methos succeded any call to service contruct resulted in an exception that "message could not be processed".
Please help me,
I can't figure out what to do.. or y it's ok on these computers specificly (all other combinations failed..  and I tried, trust me I tried)
Thank you all in advance :)