Ensure that you're entering the full domain name of your host with a period at the end if you're using a host that's outside the DNS domain.
For example if you're setting up foo.com and want to use ns1.bar.com then you'll need to set up the NS record as:
If you set it up as:
That will have the domain appended and treated as:
ns1.bar.com.foo.com
These days many domain registrars provide DNS service as part of the registration, I'd strongly suggest you use these to host your DNS rather than having to worry about things like DNS servers, zone transfers, maintaining two separate name servers for each domain (as per RFC).