You could try using the old router again if you still have it and see if xbox live works as it should.
If it does, then there might be a problem in a setting on the new router that is cauing the problem.
If the problem persists, then the xbox might be the culprit.
Also, make sure that the xbox is getting the correct network configuration. That is, if it is wireless, make sure that it is getting its IP address from your router and not your neighbours or roomates.