Welcome to WebmasterWorld Guest from 18.104.22.168
Make sure not just your web works but your mail, FTP, telnet, and gopher sites with as expected.
Record the old IP for future reference.
Then go to you domain name registry and change the two DNSes to the new ISP. Make sure you creat all the records, not just A, but MX and alias ones. Wait 48 hours for the DNS to propagate. (It usually takes less then 24 hours, but just in case there is a slow server somewhere downwind.)
Delete everything from the old ISP (using the IP address you saved).
Cancel the service at the old ISP.
NEVER, EVER let your ISP be any kind of contact on your domain names, under any circumstances. If this is a requirement by the ISP, find an other one!
I went through practically the same thing with one ISP who wound up being both Admin and Technical (before I knew better). I went through a series of threatening letters before I finally took control of Admin. Using the Admin privilege, I then removed them from Technical.
Also, don't ever close the account where you get email from Network Solutions before you change the domain info. If you can't get the email, you can't change the domain info. I strongly suggest getting the Network Solutions email at a different ISP than where you have your domains registered. That way if your ISP goes belly-up overnight, you can still change the info. You might even keep technical and admin at two different ISP email addresses (neither where the domain is parked), for better control of your info.
Realize that the email addresses in the domain listing are public information. Spammers mine those email addresses. Network Solutions also sells the info in your domain listing to snail mail spammers. So use email addresses and snail mail addresses that you can expect to get spam.