Seems Domain registrars are right when they say it could take up to 48 hours for changed DNS server settings to propagate.
If it's a record change, it depends on the TTL of that record. Before a server migration, I typically reduce the TTL to something like 5 minutes - makes migrating much easier. I bump it back to 4 or 24 hours afterward (depending on what it uses).
If it's the DNS servers themselves that got changed, that will vary based on the registrar. .com can be as fast as a few hours, rule of the thumb is however 24-hours.