Vps – Having a domain name use nameservers of the same domain

A DNS hosting service sounds like what you're after:

http://en.wikipedia.org/wiki/DNS_hosting_service

DynDNS Custom appears to provide just that:

http://www.dyndns.com/services/dns/custom/

Side note: They were the only ones that could properly register my .name domain too :)

You need to have your ns1.example.com and ns2.example.com addresses registered with fixed IP's at some registrar that supports registering name servers. It sounds like you have finished this step. These registrations are special in that they are self resolving, the IP address is returned along with the name of the name server specifically to break any circular dependencies.

However that is not the same as trying to run a dig on those addresses because the lookup system for them is different. If you would like them to resolve as normal host names in addition to being name-servers, you may add A records for them like you would any other host names in your local DNS server, but is not strictly necessary unless you actually use those as host names.

dig example.com @ns1.example.com should tell you if your DNS server is returning a records for your domain. dig ns1.example.com @ns1.example.com will tell you if your DNS system is returning records for that host name. You can also use the IP of your server after the @ to test the last step if you don't have the first one done.