You had a problem connecting again because when you now disconnected the modem, it was like pulling the plug on the router. You didn't execute a formal release of the XBOX’s DHCP lease (not that you could, it’s probably not an option on the XBOX). So it takes a little time for the ISP's administrative system to recognize the XBOX is offline and willing to give a DHCP lease to the router again. It's all part of dealing w/ changing devices between you and the ISP.
As far as the NAT issue, well now you know, it's not your router. Even w/ only the modem in place, the problem persists. As I said, it's probably your ISP, or else something else upstream of you. You sometimes see this when using a non-standard ISP, like going through someone else's open wifi, and that router is blocking ports.