Are there different classes of MBS, all with their own additional requirements? My understanding is that the business that the OP is proposing is somewhat different to that operated by BitInstant. Are they likely to be subject to more regulations as they'll actually be selling BTC direct to the public rather than operating as a platform for others to trade BTC (like MtGox) or a conduit for getting funds into exchanges quickly (like BitInstant)?
A Money Services Business (MSB) is a specific definition. There are other types of businesses (depository, securities, mortgage, insurance, ...) that may register with FinCEN.
You
might be able to get away with only registered in a single US state, if you are largely a brick-and-mortar business rather than an online business. e.g. a pawn shop exchanging bitcoins might only need to register as an MSB, plus one (1) state.
(again, IANAL, seek your own professional advice)