I switched to buying domains from Google (http://domains.google.com) two years ago. They give free private registration, let you use google for authoritative dns and setting up Google Apps is super simple.

Been a stellar choice so far!