Your DHCP server will have a bunch of IP address that it leases out to a database of MAC addresses, the problem may be that your new xbox MAC address is requesting the old IP address and your server's saying, sorry but that's already leased to the old MAC address. The length of time each IP address is leased to a MAC address can vary, just restarting the DHCP server wouldn't help, if it were a PC you could manually release it from the old MAC but it's not possible with an xbox.