This is not to be taken as legal advice, or any kind of advice for that matter, but any bitcoin exchange will have to register as a money transmitter federally and with every state whose residents it conducts business with. The fees associated with such registration are incredible. To think otherwise seems naive. Look at what just happened to MtGox. It doesn't necessarily have to do with bitcoin, but the fact that you are holding customer funds for later delivery. This is textbook money transmission.
Yup, look at California. 5K fee just for the chance to register. there are only about 25 companies registered for the entire state (google, square, western union).
You need to have an employee that is familiar with the regulations. You need to submit a business plan.
You need to spend probably 25K per state minimum for the first year, and then have at least 1 lawyer on staff, retainer with firms in all states, and train enough compliance people.
Better to go to Panama or Malta or whatever...