If I deposit some Bitcoins with a trader like Kraken shouldn't I be earning interest on my bits?
No you will not. Exchanges are not lending you any funds, you are simply depositing funds to the exchange so you can buy/sell coins.
Indeed, Vircurex does pay interests for your deposits, but I won't recommend anyone to do so for obvious reason.