Tradehill was shutdown for various regulation issues, including not having the required money transmission licenses.
What were the money transmission licenses that were required?
What other compliance rules should be followed?
Tradehill got shutdown because it went bankrupt when Dwolla started reversing money transfers made to them despite their terms of service stating that no chargebacks could occur (at the time). There is currently a lawsuit pending.
The required licenses will vary depending on the legal context and the interpretation of the business, made by the relevant legal authorities.
There is a lot of legal uncertainty surrounding Bitcoin, but there is one thing that is pretty certain : in all jursidictions you need a license to maintain fiat-denominated balances on behalf of third-parties.
There aren't many regulations to transmitting bitcoins. Probably do some extra reserach, but it seems safe and clear
Tradehill was not shut down due to a lack of money transmission license.
But to the point of your question of what is required to maintain compliance, no one can really answer that as it depends greatly upon jurisdiction.
Now, IMNAL, but I would say that a general rule is that if you are operating an exchange, you probably are playing with fire in a legal sense. There are a lot of organizations worldwide that will claim authority over that type of business.
However, a company like BitInstant and Coinbase are probably more in a safety zone for the simple reason that they are buying and selling their own stock of Bitcoins rather than doing so on behalf of a third party. This falls much more under local jurisdictions and licensing requirements would vary greatly. Does it require a money transmission license to operate this type of business? Maybe. It depends if the jurisdiction considers Bitcoin to be money or commodity. If it considers Bitcoins to be a digital commodity, then you probably just need a business license, and perhaps a sales tax license. If it considers Bitcoin to be money, then you likely will need a money transmission license, currency exchange license, or even potentially a banking license.
Again IMNAL, and you should certainly consult one before starting any type of business, let alone one in the Bitcoin arena.