I've got a VPS at GoDaddy myself, but that domain name is registered with Names4Ever/APlus.net. What I had to do to get DNS working was to send N4E an email telling them the IP address of my DNS server(s) (ns1 and ns2 were on the same box) so that they could be registered with the root servers of the intarweb.
Once that was taken care of, all my DNS problems vanished.