Trust is a tricky thing. It sounds great when you say that somebody should earn your trust, but let's think it through! Eraning your trust means in reality that you basically do not trust!
Let's assume that he/she does something great - can you really trust him/her? I think you cannot! Because that was past and he/she may screw it up next time...
I do not believe in earning trust! Because there will always be a shadow of "but what if...".
There is just one way to get around: you should simply trust him/her, without conditions. That's actually what trust is. And if you can do so - may not be easy! - them you can free up both him/her and yourself!
Therefore I have bad news for CIOs who are not trusted by their CEOs, as CEOs best move is the replace the CIO with somebody they can trust.