The token must have the DNS:Edit permission.
DNS:Edit
That is different to Zone Settings:Edit.
Zone Settings:Edit