Existing banks could, I suppose, go into this business. But the experience of the IAFCU--being given an excessively hard time by regulators when they started working with BTC businesses--is why they don't. Banks exist because goverment regulators allow them to. Unless they are extremely large (and then the government regulators exist because the large banks say they can, evidently.)
I am a BTC skeptic. I don't think it solves a burning problem for most people. But the government, in trying to keep BTC from succeeding, seems to be creating the very raison d etre, solvable only by crypto-currency, that BTC was lacking.
As long as the US Gov is against bitcoin, and they should be for their own sake, they will make it impossible to comply with the regulations. Anyone involved in creating the bank would probably face criminal sanctions for some crime. Crypto currencies may eventually threaten the USD's status as a reserve currency. The US Gov will do anything possible to stop bitcoin from growing to that level.
Some banks (depending on the location and size) keep foreign currency on their books so you would just need to account for it by the same manner unless there is some definition as to what constitutes a foreign currency for accounting purposes.
Anonymity? Nope, KYC (know your customer) rules would require ID of all wallets.
Untraceability? Nope, AML (anti money laundering) regulations would anyway require you to identify the source and 'final beneficiary' of each transaction; and deny/freeze a bunch of transations matching some criteria. Oh, and you'll be financially liable if you're too soft on verifying which of your users lie.
Finality of transactions? Nope, payers can contest payments for all kinds of reasons, and you'll have to return money to them; But you'll not being able to get fraudulent payments back due to properties of Bitcoin.
Doesn't look like a good business to me; you can be profitable as an unregulated exchange, but doing it "properly" will make you completely uncompetitive.
But yea it's all a game of risk and how much of it they are willing to take. Bitcoin businesses are in the highest of high risk categories and they currently don't bring in enough money for the banks to justify the potential downsides.
At this point any US based entrepreneurs should consider looking elsewhere for banks. I know of a Caribbean country planning to be a haven for cryptocurrency businesses. Things will be announced soon.
No one spent a day in prison for these acts, no bank was disbanded as a result, no bank officials were reprimanded, which seems to be blatantly unequal when the big picture is taken into consideration.
Then there is the fact that the USD is backed by nothing other than military might...