This does not sound like a network issue. To troubleshoot, I might try taking one of the machines in the lab to the same subnet as the netboot server and see if it works. The only times i have had those sorts of spinning globe errors was when there was a problem with my image.
Netboot can work across subnets, but it needs some help. The protocol that is used to locate a netboot server is not routed. So your network guys have to create a helper address to forward the netboot broadcasts to the Netboot server.
Shea