If you host your domain registration, DNS or web site with Network Solutions, you should change your password immediately.
Source: Network Solutions | Important Security Information
This breach also illustrates why it’s important to use different passwords for different accounts. If you have used the same password for any other accounts that you used for your NS account, you should change those passwords too.