Okay, that's a royal pain in the butt, but we can fix it. So, I update all my DNS settings, get my secondary DNS providers updated with the new IP, and we're all good, right?
My ISP didn't duplicate the firewall settings that my old IP had, so nearly all incoming traffic is now being blocked at the router. Nice. Hopefully we can get this fixed soon, since I can't receive e-mail (among other things) until it's resolved.