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 ?
Edit: check the router settings for something preventing comm or read its docs. This should not be happening if they're all on the same subnet.
See if you had disabled discovery by other machines on the windows os that would create the behavior you're talking about across the board. Meaning wired and wireless connections would not be able to "see" one another, meaning windows wouldn't reply to pings. If you had firewall settings that blocked all incoming traffic that would prevent other connections. You might check your adapter settings on the os, as maybe that is where the problem is happening but I doubt it. A quick search on that level is not revealing anything.
But simply switching between wifi and wired should not allow this connection to suddenly occur. Its the same network series of protocols in the stack above the ethernet/802.11 layers.
With your update I would suspect the adapter settings.
Do you have a usb drive you can place a linux iso on ?
If you do, make it and run the thing in the scenario suggested and try to do a ping then.
If you do that and it works its windows.
More later after you try this.