Changing DNS for .dk domain

I have quite a few domains with OVH. I use OVH only for registering domains and have changed the DNS servers for all of them to my hosting provider. I recently bought a .dk domain and I cannot seem to change the DNS for these. I can change them in the DNS manager just fine but I get an email after a few minutes informing me that the change did not succeed.


An error occured during the the DomainDnsUpdate n° 3624xxxx procedure associated with the xxxxx.dk domain.

The next message was send by the robot who checks the procedure with zoneCheck:
Dns failed: Internal error, Internal error, Internal error, Internal error, Internal error


I try to add 3 servers after which I want to remove the 2 from OVH. One of the things I find odd is that I get 5 internal errors (for the 5 DNS servers) because if I just add 1 I get 3 errors so I assume that even the OVH DNS servers are considered incorrect. I get send to a page with a tool that does not help in resolving this. Does anybody know what I need to update on the new DNS servers so that I can move this domain to my DNS servers?