Because you can't lend out a Bitcoin you don't have, unlike fiat currency.

This is like saying you can't lend out a dollar bill you don't have. It's strictly true, but doesn't accurately represent how the banking system work. The $1,000 dollars in my Charles Schwab account don't correspond to 1,000 physical dollar bills somewhere. They are simply a number in a database somewhere. When I go and withdraw that money, I get back a random selection of $1 bills that other people have deposited.

A bitcoin bank would work the same way. You deposit bitcoins by sending them to the banks wallet. They put a number in a database saying that you have 20 bitcoins in your account. If you then withdraw it, you will get a random selection of bitcoins they have in their wallet.

Unfortunately fractional reserve isn't safe for a currency that is this volatile. Depending on what the "fraction" is, some major withdrawal demand against one of these exchanges would topple it

So you are a Big Fish. You have a boatload of money in exchange X. You go to take it out and they don't immediately give it to you. They say, "Listen, we can't get to it, it's in our cold wallets, it will take a week." A week goes by, they say, "Listen, here's 10% of what you asked for, we'll get you the rest shortly.". This goes on, they periodically give you some of the money but there's a lot of evasion.

What's the Big Fish to do?

a) Quietly keep pressure on the exchange, taking the money as it comes, while not putting any back into the exchange.

b) Make a big stink, bring in lawyers, write press releases and bring down the exchange, possibly destroying any opportunity of getting the money back.

A is obviously the choice here... but that's a problem if you have a lot of big fish trying to get their money but can't. The price should be tanking, but everyone is too afraid to trigger a run on the exchanges that would kill their investment. There's really no way to know if this is happening. It could have already started.

Move coins to another exchange

How? They have your coins.

Yes, that is precisely what the problem is. There will one day be a run on the exchanges and it will get nasty very quickly.

But as an exchange, you can lend out Bitcoin you have, while still displaying unchanged balances on people's accounts. So you have a fractional reserve.

Couldn't they do it partially by betting that not all their customers would withdraw their funds simultaneously? Lot of less technically inclined people seem to keep their coins on one exchange like Coinbase

But then if this was true, that would mean the real bitcoin supply is actually worth more than it is now.

Good point. I am taking for granted that people will have their coins in their wallets, and lot just leave them up on an exchange.

how many people do you think keep their bitcoins in wallets vs on exchanges?

don't know, but I would think leaving it on an exchange is a terrible idea (Mt. Gox)