I was having a similar problem. Both my brother and I have an xbox 360 and forza 4. We live in the same house right now, so instead of just playing split screen and only being able to use cars from one person's garage, I'll bring my xbox up to his room with a little tv and we'll race over the network.
The problem we were having is that 9 times out of 10, I wouldn't be able to join a lobby he created, or vice versa. Checking our router settings, it says our NAT is set to open, but when the problems occurred, the Xbox kept telling us it was moderate or strict, not allowing us to connect.
The only thing we tried, and it has worked both time so far, is turning both Xboxes off. Then going over to the router, and resetting it. Then turn both Xboxes back on. After that, each time, we were able to connect right away and race.
I think it might have something to do with IP addresses or something. Maybe, by turning both xboxes off, and resetting the router, it gives each xbox the same IP address.
Of course, my solution only applies to two or more people in the same house/building who want to race each other...