It never occurred to me to try the WRT54G2 by itself.
I just unhooked it from the Actiontec, enabled the DHCP server on the WRT54G2 and tried the DhcpAddressPrinter again and "Failed to configure Ethernet using DHCP" came up again in the serial monitor.
My original configuration has the WRT54G2 connected Ethernet to Ethernet with the Actiontec. The WRT54G2 is setup in Gateway mode with a static IP address. DHCP is disabled on the WRT54G2 and anything connected wirelessly to it gets its IP from the DHCP server on the Actiontec. I had to do this due to my xBox not connecting to the Actiontec for whatever reason.
Either way I hook up the Arduino, WRT54G2 or the Actiontec, DHCP fails.
I've tried three different cables, two different routers and every configuration I can think of involving DHCP and Static IP.
I'm beginning to think the Ethernet Shield is bad.
And Tim, thanks for the help so far. This is driving me insane.