So the only other thing I have going on with my home network is a Linksys WRT54G2 router (setup as a Gateway). This router was set up via ethernet cable from the Actiontec to ethernet port 1 (not "internet" port) of the WRT54G2. I did this because like the Arduino, the xBox absolutely would not connect to the Actiontec router via WiFi. So, after I hooked up the WRT54G2 router, the xBox immediately connected to it over WiFi and thus the internet...oddly though the xBox shows up in the Actiontec as an "ethernet" connection and not a Wifi connection.
Regardless, I tried plugging the ArduinoEthernet shield into the WRT54G2 router and the same thing is happening...Failed to configure Ethernet using DHCP.