Sorry for the outage everyone. It was our DNS provider, ZoneEdit. Not impressed with their service!
Cloudflare is a great service, but it's a CDN and would not have helped fix the issue we just had.
Everything seems up and running and OK now, we'll be taking steps to move to a new DNS service as soon as possible.