And what profile is your network, home/private or public?
You changed out your gateway with a new device, so the mac address will change even if using the same network ip space, its almost a given that windows will see this as a new network.http://technet.micro...5(v=ws.10).aspx
When windows sees a new network, it should ask you what type of network.. So what did you set it too? Or when you first setup windows and it asks you what network this is, and you say home/private there is also option to treat all other networks as public. Did you set that option so you wouldn't even get asked?
Here is the thing, if you can not ping the other machine by IP.. Look at your mac address table with arp -a, do you see a valid mac for the IP your pinging? If not then you have something else wrong.. If you see a valid mac, its more than likely firewall related.
I would say your windows firewall is on because your in a public network according to windows. Or if not the windows firewall, some other security software blocking ping based upon network awareness.