What OS are you using? When I was playing MechWarrior 4 (another game released/sold under the M$ name) I was using Windows 2000 and I couldn't play with anyone using Windows 98. I think we got it to work maybe once, that was it. I formatted the drive and re-installed Windows 98 on it and it worked like a charm.
Don't know if this is what's affecting you but thought I'd pass that along.
ST