The problem is that my main domain name is registered with directNIC.com. I was trying to register name servers by sending host form to Network Solutions several times, but the reply was:
"It appears that the request we received was not submitted from an appropriate e-mail address."...

I am listed as administrative, billing and technical contact for the domain with the same email address I used to send registration form.
Is there any way to solve the problem?
Do they register name servers for domains registered with another registrar at all?
Any help would be appreciated, thanks.