The DNS servers now seem to be up intermittently. The GoDaddy site still lets you modify the name servers, so I pointed a few domains at Route 53 and because the NS records have a very long TTL that fixes it for most of the customers once their DNS gets a single query through.
GoDaddy confirms the issue, seems to affect EMEA area DNSs only <a href="http://support.godaddy.com/system-alerts/" rel="nofollow">http://support.godaddy.com/system-alerts/</a>