Domain Mapping plugin

I'm using the latest Domain Mapping plugin (Version 4.4.2.4) and trying to map to a TLD domain; the DNS is correctly configured with the correct A record. The domain is not 'new', not a recent purchase. Yes, I have a dedicated IP address, and I'm using Cloud VPS. I have gotten this to work in the past, but this is intolerably slow - it has been more than 24 hours and I am still getting the red box response that "the domain is unavailable to access". This creates a very awkward situation with the client - I consider it unacceptable. That said, I'm willing to consider that "I'm doing something wrong", thus my question here: Does the client's TLD domain nameservers have to point to my hosting account? I am under the impression that the only update to the client's DNS records is to change the A record, is that correct? Or do the nameservers also have to be changed to my nameservers?