after reboot, network is lost

Hi,

I am facing a strange problem in my office LAN. When I reboot any
computer, network connection is lost. There are 2 ways I could find to
get away with it
1) ping <gateway_ip> for about 10-15 minutes and the network is
restored.
2) remove network cable and put it again. Network gets restored after
2-3 minutes.

Once, network is restored, it works without any problem till I reboot
next time.

Has anyone faced similar problem already?
Can anyone suggest me ways to troubleshoot actual root cause of this
problem?

Currently I am using Fedora7 as desktop OS

Thanks,
Ravi