Something else you might consider is Speedlite Softbox (Commercial Link Removed) instead of the umbrella.
Although sometimes you want the spill of an umbrella, I more often use softboxes instead. Although there are many brands to choose from, Photoflex products are both well-designed and reasonably priced. Plus, local camera stores tend to stock of lot of Photoflex. They also make fabric eggcrates for their softboxes (highly recommended for light control). Plus, they make speedlight brackets for softboxes too. Westcott also makes some really cool lighting control products (softboxes, collapsable silks, etc.), as well as a nifty flash bracket.
On the other hand, umbrellas are fun, too--just try to get a really big one!
Actually, I haven't used any of my umbrellas or softboxes in quite a while. Mainly, because they're all just too small (resulting in too-hard shadows). A 4' x 8' piece of Foamcore (or, even better, two pieces of 4' x 8' Foamcore, for an 8' x 8' source) makes for a much larger source for bouncing (albeit, with no control) than all but the largest studio umbrellas or softboxes (but for a little punch in the eyes, I also own a small silver umbrella, in addition to a 60" white one).
I would also pick up at least two C-stands to mount your bracket and other lighting gags onto. Matthews makes them in black also, and at least two 25-lb. shot bags (shot bags are more compact than sandbags). Or, if those are too steep, the (non-air cushioned) Photoflex light stands are pretty cheap. Matthews also makes a couple of cool brackets to mount Foamcore sheets to C-stands.
Aw, crap! I had no idea this thread was four months old! Shiva, what did you end up getting?