For the sake of completeness, let me note what the status is on this: It turns out that the DK Hostmaster doesn't have the ns1.dreamhost.com (etc) names registered, and since they need to be registered before a .dk domain can be hosted there, these names can't be used. - They're not registered because DK Hostmaster is the only hostmaster in the world to charge money for registering, and Dreamhost isn't interested.

Solution: Instead of ns1.dreamhost.com (etc), the OLD host names should be used:
ns.newdream.net
ns2.newdream.net
-- These are registered and they work.

Before I can redelegate my domain to these DNS hosts, I must first add the domain to Dreamhost's servers:
https://panel.dreamhost.com/index.cgi?tree=domain.add_domain&
Once this is done (once my .dk domain name is registered with Dreamhost), then I can redelegate the domain with DK Hostmaster. They do a reverse lookup and they won't accept the redelegation request unless they can see that the new host (ns.newdream.net) already has the domain listed.

All DK Hostmaster requests are via the web and fully automated. They do have a phone number, and if you're patient (waiting in line) and friendly (to the operator) then you'll get fine service.

I'm now just waiting for things to be updated all around and hope to see my domain redelegated soon.

-- a happy-hopeful Dane