Right off the top of my head I'd say IPtables on your new linux box is the problem. By default, RHEL versions do not just drop packets silently, IPtables issues an icmp destination unreachable if packets do not match any rules. With that said, it sounds like your running VMs (Windows and Linux on one box?) and the issue may also lie in the network configuration of your VM host. Can either of the machines reach the Internet?
To quickly verify if IPtables is the culprit, you could do:
'/sbin/service iptables stop'
Posting the output of '/sbin/iptables -L' will help too.