Make sure that you are performing a factory reset as described in this article (http://support.slingmedia.com/get/KB-005036.html).
It sounds your Slingbox still has the old router's network configuration. Performing a factory reset will wipe out the configuration settings, and allow the Slingbox to get a new DHCP address from the new router. However, if it is still unable to get a new address, you might consider a couple of things.
First, if you're using a third-party linux router software, you might consider restoring the original manufacturer firmware. I've helped several people on these forums, and it seems that DHCP protocol that some of these boxes is not using the "standard" DHCP protocol. In almost all cases, either a firmware update was in order, or restoring the manufacturer's firmware resolved the problem.
The last thing resort, is to reconfigure the router to use the old router's network configuration. That inluced its private IP address, Subnet Mask, and DHCP scope of addresses. The idea to change the router so that it matches the configuration setup still resident on the Slingbox.