Is your NAT type set to open? This can be checked from your Network settings in the actual Xbox One settings app. Reading other forums i've heard nothing but great reviews on the matchmaking and how much better the experience has been than the MCC launch. So it's surprising to see two people mention connectivity issues.
If it's not set to Open you can login to your Router and change it by (usually) visiting 192.168.1.1