For clarification, the Arduino IS connected to the laptop via USB (for serial communication). The shield is connected to the laptop via Ethernet (and sharing the wireless connection of the laptop to the router...or so is the intention), simply because I don't want to do my development in the cold, dark basement where the router is!
I suspect it has to do with the Internet Connection Sharing, so my first test will be to plug the shield directly into the router and see if that works.