SPF DNS Error / R_SPF_DNSFAIL

Hi list.

My incoming messages are getting R_SPF_DNSFAIL and an error on the Authentication-Results header:

spf=temperror (mail01.r3pek.org: error in processing during lookup of no-reply@cttexpresso.pt: DNS error)

I see the DNS request on my DNS server and a "working" reply going out. What can cause this error and/or how can I debug it?