Can't connect match in exhibition

I tried to play a set against another Steam user from South America. We couldn’t connect. My connection seems to work ok. I have no idea how to deal with PC connection stuff (whatever it is…Firewall, teredo, or whatever black magic).
The thing is I think it’s not on my end since I can find matches with ease and this person told me he didn’t find as fast as me. Could be something about his settings?

Not sure. The few times I’ve done Steam to Steam exhibition sets, the invite system has worked just fine.