Use dig ( dig @< authoritative nameserver > < host or domain > would be a start) to see the current settings of the authoritative nameservers for the domain. They may not have picked up on the changes yet (for nameservers associated with hosted domains the records you can edit are often not the ones on the public nameserver but are copied to there after validation by a process owned by the hosting company; it's different in some cases or if the nameservers are actually your machines, of course). Even if the primary nameservers for the domain have the new information, any other DNS server that has recently resolved the domain and received the old information will have cached this for the TTL time and will not resolve the domain again until that expires (this is the reason for reducing the TTL time well before making a DNS change if you have control of that record (older versions of BIND set the TTL in the SOA record; TTL can also be set on an individual resource record)).
You can use dig ( dig < host or domain > )to see the records being returned by the nameserver your client is using, that should indicate which version it is using and the remaining TTL.
(I'm referring to dig above assuming you are using a GNU/LINUX/BSD client but I think there is a version of the tool on other platforms, too)
(I also started writing this wrote before reading your edit -- is that how it was originally set up? -- If so it could still be a caching issue, the TTL times should give a good indication of this. Unfortunately I have not familiar with DNSStuff is or its outputs so can't help there)