Depending on registrar, it isn't always simple changing NS entries for a domain that is being used as a name server. You may need to fax a letter w/ a copy of a picture ID.
2nd, make sure you have your hosts correct name servers.
3rd, Do you have other domains using your "main" domain as the name server?
When all these are known / ready, set your "new" nameserver, your hosts, as the primary and keep your secondary (ie: ns2.yourdomain.com) as your secondary. It should start resolving within 2 days. When you are sure, set your secondary nameserver to your hosts.
You will have to do this w/ all domains on that box.
__________________
|