I switched to fastmail from gmail a few months ago and I'm incredibly happy with it. I even got to keep my *@mydomain wildcard addresses, and the fastmail calendar implementation is not half bad.
Were you using Google apps for your domain (or whatever it’s called now)? And if, were you able to maintain access to your Google docs and other Google-based services (play, etc)?