I kind of go with one of the comments here, that doesn't make sense. If you're able to perform network discovery on the machine from another windows machine, icmp is going to work the same on a Linux box.
The only thing that could be happening is the router itself is blocking traffic between the machines.
That is the only point of failure of a crossover connection works between the machines in question: the transmission medium and network appliances servicing it.
You're not using VLANIng or anything right ?