Do you have the correct NAT and forwarding options set ?
I use :-
-A POSTROUTING -s 192.168.1.0/255.255.255.0 -o eth0 -j SNAT --to-source <public IP>
If nothing else on your network has that IP (demonstrated by your ping) then it's a nat/routing issue that is preventing your ve's from accessing the internet.
Also, I went to the trouble of looking the MAC address up
MAC Address
Prefix Vendor
0017E0 Cisco Systems
It looks like your cisco router is doing as I suggested and proxy arping.