First of all, I suggest you run an experiment in a controlled environment to see whether my theory is correct. After that we can start looking for the problem.

Have one of your friends join your private server and see what happens. After that, have him host a private server and join it. See what happens. I'm particularly interested whether any of you can see the other player in each case. Report the findings to me and I'll see what I can come up with. Also, be sure that this friend isn't having any hosting and/or cto problems himself.

~Ol