The DENIC registry's requirements for nameservers are fairly strict, but do not necessarily make the requirements clear when an attempt to update them fails.
You can test your domain and nameservers here: Nameserver Predelegation Check Web Interface
Once making the necessary updates based on the tests, the update should proceed without any further issues.