I had this problem playing dota2 using the same internet. Searching on the forums, I found out that DotA2 uses as default, port 27005, but it can range from 27005 to 27032, so I could set my port to 27006 and my friend at 27007, so we could play in the same game.
I changed the port by selecting my games library on steam, right click DotA2, properties, Set Launch options and typed +clientport 27006 to me and +clientport 27007 on his computer.
But the age of empires 2 port range is a mistery to me... I'll tell you when I found out.