How long should it take to rebuild a wheel?
I think if you are willing to spend a few hours, it's worth doing yourself.  Depending on the flange size of the new hub, though, you may need to buy new spokes.  You can determine the length of the spokes you will need using a spoke length calculator.

You will need a spoke wrench, a flat-head screwdriver, some vaseline, and the use of a truing stand.  Here's what you'll have to do:


Remove the tire, innertube, and rim tape from the wheel.
Using a spoke wrench, loosen and remove the nipples.
If you are using the same spokes, remove the spokes from the old hub.
Lace the wheel, making ABSOLUTELY CERTAIN that the valve will be in the right place.  Check out Sheldon Brown's step-by-step wheelbuilding page for the procedure of lacing a 3x (three-cross) wheel.  You will want to use a little bit of vaseline on the threads of each spoke so you can tighten the nipples more easily.
Go to a nearby bicycle cooperative (you can google bicycle co-op near nameofyourtown) to use a truing stand, and use the truing stand to adjust the wheel.  Make sure the wheel is dished properly and that you have proper tension on the spokes.


Because spokes stretch a little and settle in after you start riding, be prepared to true the wheel after the first couple rides.

If you are not interested in making your own wheel, I recommend just buying a new wheel with the hub you want.  It may be cheaper than getting your lbs to rebuild your wheel with your new hub.