People associate google with search. To get them to change, you have to offer them something better/more than google. And if you're microsoft, it's an uphill battle, because most users hate you, so you'll have to be even better than that.
Remember: If you're reading Hacker News, you're not a "typical computer user". You're not the type of person that's lining Google's pockets -- you're probably a cost.
Most "typical computer users" don't hate Microsoft. They're happily using Word and IE, love FreeCell, and couldn't tell you what Emacs or The Gimp were to save their lives. People stopped reflexively typing 'yahoo' and 'altavista' pretty easily when their friends recommended 'google' and could do the same for 'bing'.
Keystrokes aren't a switching cost and Google isn't nearly as invincible as you might think.
Let me quantify a little more... People associate microsoft with bad things, and the past - their operating system crashing and dying. It's a necessary evil for them (Until they discover linux/osx if they ever do). Google on the other hand is associated with providing good search results, and allowing them to find what they want to, quickly.
I agree, google isn't invincible, but I believe if it is to be replaced, it'll be by a startup. Not a rebranding of a god-awful search engine by microsoft.
>> "That's 'better/more' enough for the typical computer user."
It's really not. You're talking about changing everyones behavior. Why would they do that? Because it looks prettier? You're delusional.
Don't intend to start a flame war but this is ridiculous. How do you explain ~95% of desktops in the world running windows? As far as discovering linux/osx is concerned, it isn't for the common computer buyer yet. It is the computer scientists/hackers who discover them. Most of the common people probably haven't even heard of linux.