Never used CenturtyLink personally, but a few things it could be:
- Some ISP's have sticky MAC address learning and will only allow 1 MAC address on the port. You may need to wait a few hours for it to forget the old router and accept the MX
- It could be an MTU issue - I think their side should be configured for 1492 but don't quote me on that.
Either way you're best calling up CenturyLink to see what they are seeing on their side.