We recently had to change the our DNS servers ... the change has now largely propagated 36 hours later, but Facebook still is not able to resolve our links. My guess is Facebook takes a while to purge the cache on its DNS servers ... any idea how long it takes for them to do that?
How long it takes to propagate depends on TTL values of the NS and corresponding A records on the old DNS server. Only you know what the TTL was - could be from minutes to weeks.
In some cases of misconfiguration default TTL value stored in the TLD zone may take place, which is always 48 hours for .COM and .NET domains.
Facebook should not be any different from anything else.