Domain was from 1and1, sent the domain to use my VPS as name servers which worked, as shown in my Whois.
There is a domain holder file on the VPS which should be accessible. However I cannot get there unless I use a proxy. I did a check of the domain on HostTracker and got 2 Succeded and 36 failed checks.
What would be causing this? Is it simply because I recently changed the DNS settings and it takes a while for it to fully work?
Typically 24-72 hours depending on your ISP. My ISP at home, RCN, takes a long time to update their DNS caches. I currently use OpenDNS instead. Basically what you do is change your DNS Resolvers from your ISP's to theirs, so your DNS updates instantly - because they dont cache the records like my ISP does. Their site is http://opendns.com - check them out.