DNS Enhancements: Prime Infrastructure 3.9 has brought security to DNS traffic by implementing DNS Security Extensions (DNSSEC). This is enabled by default and can be controlled through new Admin CLI option - 'ip dnssec'.
Disabling dnssec was the solution in my case:
hostname/admin# conf t Enter configuration commands, one per line. End with CNTL/Z. hostname/admin(config)# no ip dnssec