Can a mobile be protected against the "Linode problem"? The "Linode problem" I'm referring to is where an external trusted party has administrative control over your device.

Mobile phones are essentially managed devices.  They can be fully controlled by someone other than the owner of the device.

Yes, they are managed by the carrier but possibly that carrier has people that cannot be trusted or, something just as bad, has people who don't maintain secure systems themselves such as what reportedly is what happened at Linode.

The importance is this.  Consider Safaricom's M-Pesa mobile payments system used widely by those in Kenya.

An attack that defrauds M-Pesa's users en mass means that at some point Safaricom figures out that there's a problem, halts all affected systems to prevent further losses, and in the end eats some, most or all of the customer's losses.

With a mobile app like BitcoinSpinner, or My Wallet from BlockChain.info or even a hosted service like Paytunia's online wallet, the risks are quite different from M-Pesa's.  The carrier doesn't promote the Bitcoin app nor offer any guarantees.  A similar attack through the managed services of the mobile carrier's network to steal bitcoins from mobiles would cause the finanical losses to afflict the individual mobile user alone.

Just like how Linode disavowed any responsibility to Slush, Bitcoinica, etc. for the tens of thousands of bitcoins lost, carriers such as AT&amp;T, Vodafone and Safaricom would likely maintain the same type of position.

So, this is a fundamental question -- is the practice of storing bitcoin private keys on the mobile something that exposes it to so much risk that it shouldn't even be considered (at least, not for amounts greater than the amount of cash one might carry in a back pocket?)

Or are there ways to secure a mobile device so that even if some piece of malware is deployed by a carrier's rogue employee that the bitcoins would still be secure?
If your private key is compromised your coins are gone

So the short answer is that the "Linode problem" where your entire private key is at the mercy of a third-party capable of root access to your system is somewhat intractable. As others have stated you can limit your key's exposure, but malware is patient.

Off topic, but possibly of interest, is a project by the MultiBit team to use a HP50G scientific calculator as an item of trusted hardware capable of signing transactions. Not much use out in the field like a mobile would be, but handy for a small business reconciling small volumes of transactions.