I'm guessing the problem lies here then:
lxpack.pt/DNSKEY: No response was received from the server over UDP (tried 12 times). (94.46.135.14, 94.46.135.27, 94.46.135.88, 94.46.135.114, UDP_-_NOEDNS_) lxpack.pt/DNSKEY: No response was received from the server over UDP (tried 4 times). (94.46.135.114, UDP_-_EDNS0_512_D_KN)
Because the other warnings lie on our own NS (as this is a CNAME pointing to one of our domains), and all other certificates get issued just fine. I'll try to get in contact with the owner of the lxpack.pt domain.
Thanks