A little more info on my situation that I should have mentioned:

- All of my boxes are using bind as a cache-only nameserver, they
aren't hosting any domains themselves.
- The domain in question is registered with netsol.com, and thats
where I updated the list of authoritative nameservers.
- This update was made 1-2 months ago at this point.
- Using dig, host, nslookup, ping, or any other tool to resolve the
ip, they all use the old set of nameservers. The one exception is 'dig
+trace', and that doesn't affect any future lookups. Only a restart of
the process (or the box) lets the cache get updated.
- The TTL's of the domain entries are the the issue, they are all
pretty short (less then a day), and once they expire it simply
contacts the old nameservers again and gets the same old (wrong) ip.

If there anything else I can clarify, please let me know.