We don't have an army of PR flaks, spin doctors, marketing mavens, and advertising reps like The Other Guys do. Performance Computing magazine Microsoft has been very successful convincing much of the North American populace that any computing job can be solved cleanly and easily, if you only throw enough NT servers at it. Many people who have never heard of Linux will probably be interested to know that alternatives exist. Microsoft's recent problems with US federal and state governments have called public attention to the company's unfair business practices, and many people will at least be open to listening to alternatives. Emphasize Linux's popularity, its growth, and the fact that it's trusted by a growing number of companies and government agencies.
Nobody likes to be rushed.
Give them enough credit, that they'll know themselves about the limitations of what they normally use. To those who believe that even bad attention is better than no attention, being treated as a non-entity can be the most frustrating attitude of all. Because of the low cost of getting it, people can try out many versions, many distributions, before settling on one. Some CD makers, in place of an update contract, simply sell subscriptions to their Linux CD packages. All this makes it very, very difficult to accurately count exactly how many computers around the world boot Linux.