Are bitcoin wallets money service businesses (MSB)? Do hosted wallet services located in the USA need to register with the fenCEN as a MSB?
If the business is based in the US, yes.

Edit: IANAL, but in my opinion a wallet service clearly falls into the category of money transmitter according to FinCEN's virtual currency regulations.