I would try turning on UPnP... did that at my friends house and everything started working.
I think most problems are caused when both parties are behind a router (and even then it only happens with certain routers, as I can do it just fine).
You seem to have all the ports open Apple recommeneds, have you always been trying with the same person?
Do you have a firewall on your Mac on as well?