* reassure users that the service was "merely" unavailable and no data was lost (i think you already do this)
* explain specifically what happened and why to the best of your knowledge (i think you already do this)
* explain specifically what you're going to do to ensure it doesn't happen again, within reason
* if the downtime is extensive, give paying users a free month or whatever of service (i think you would already do this), within reason
If you pay X for a service, generally you'll have an idea of the service level and value you expect. I think most people are reasonable about this.
Customers that go off the rails (no pun intended) because of an outage in a free/inexpensive service are probably customers you don't want to have.
http://www.37signals.com/svn/posts/800-what-happened-this-mo...
(Although the Rackspace comment might have been a tactical error).
I was impressed with the post today, is why I commented.
http://en.wikipedia.org/wiki/Places_in_The_Hitchhiker's_Guid...