The latest patch has been a dramatic improvement for me. I was actually able to play a match today, having been trying since Monday. In fact I was able to join most of the games I attempted (not counting the ones where I received a "fail to connect" before the attempt was even made).
When hosting my own game I noticed that some players remain on the NAT connection screen for a while even after you kick them. I also noticed that some players seem to be 'unkickable.' These players just hang out on the connection screen for several minutes. Has anyone else noticed this? Is there a solution?