I did this a while back...
I did look at Hivemail - it looks quite cool but it is no longer being developed (which isn't that big an issue).
I wrote a custom sign up script that allowed users to check availability against the domain names available and then sign up (it all went through instantly by using payment through Nochex and because our email accounts are done in a MySQL table).
Deciding on the actual webmail system was quite a difficult one...
I toyed with a number of packages but settled on
IMP (part of Horde). It is quite fiddly to set up but it's been rock solid. The newer version has a front end in development called DIMP which brings in a few cool AJAX features. You can also use some of the other Horde stuff to give the users a calendar, address book and virtual filestore.
My second choice was
DWmail - this is a lot less complex than IMP. It's only £20. Pretty good though.
I recently saw
Roundcube which looks pretty cool and is very Web 2.0. It's still in Beta but it does look reasonably solid.
There are plenty of other webmail clients out there... Off the top of my head Squirrelmail is very popular, but I never liked the feel of it and I couldn't find a decent skin for it.