Actually, after posting this I found an article that said that GoDaddy is selectively denying DNS requests, so they are now being crappy with DNS as well. I guess I need to move to a new registrar and DNS host.