Just had exactly the same problem myself. Me and another guy was blocking each other. When I was online, he couldn't get on, but when I came off he could and while he was on I couldn't get on. I did notice though that my FSNav was connected.
I went to my router and checked my ports. I had the FSNav port forwarded but not the ones for FS. I forwarded the UDP ports 23456, 6073 and 2300-2400 and it was ok. We could both get on ok at the same time.
What I can't make out is that even though I didn't have these ports forwarded, I could get on, but was obviously stopping this other guy. Also, it had never been a problem before, but then I did adjust my router settings the other day to fix my IP address.
The other solution obviously could also be to put your machine in the DMZ, if available. That way, you shouldn't have to mess around with forwarding.