I tried again this morning before work and got it to connect to the router using the example DHCP sketch. I quickly uploaded the Teleduino sketch and got Teleduino to work also (ping, set digital line, turned on an LED, etc). After about 5 minutes the service stopped working.
At this point I went ahead and uploaded the example DHCP sketch and again the serial monitor said Failed to connect.
Could this be a sign of a bad Mega or Ethernet Shield?