Inability to join games in an Xbox Live party

So I can play MNC just fine by myself but when my friend and I create an Xbox Live party and attempt to join a crossfire game together, I get an error. This error is: "Unable to connect to host". He is able to join the game just fine and I still get that error when I try to join his game through his profile.

Similar problem here, only I can't even create an xbox live party and can only join a party successfully about 10% of the time. My Nat is open and ports are forwarded for my xbox live compatible belkin router. Edit: My router is a Belkin F5D8236-4 v2. I can find and play games fine by myself, it's just when I try to party up with friends it will not work.

Help.

This is a real problem. I love the team play in this game, but getting a group into a stable game takes forever. We'll go through several instances where everyone but one will successfully join a game, so we'll have to regroup. Or we'll join a game midway, and be on separate teams, and then the host will quit and we have to reform the group and repeat the process. At a certain point, fighting the matchmaking system overcomes the desire to group.

Is there any way these issues can be alleviated? At the very least, can you make disconnects kick the group out into a shared lobby so we don't have to reform each time a host disconnects?