DNS wasn't really the problem here, it was the hosting and setting up a ssl cert. I use GoDaddy for my DNS stuff and have never had any problem with them for that. Most of the horror stories come from people hosting with them.
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.