Yes, to gain traction, Bitcoin would have to be used in a way that appeals to both sides of the market. Both sides have to somehow share in any savings that it brings.
It also has to be significantly better than the status quo. There are many markets where using Bitcoin currently doesn't have a significant advantage over the existing payment options, I think. In fact, I'm fairly sure there is often a net greater cost spread across both parties if they use Bitcoin, if you consider the case where someone exchanges other money for bitcoins in order to pay with bitcoins, and the merchant exchanges the bitcoins for other money.
However, and this is an important point, Bitcoin does not have to be suitable for all markets worldwide to establish a presence in some markets. In fact, it doesn't even have to appeal to every merchant operating in a market - just to some of them, perhaps those with the lowest profit margin. If Bitcoin is to succeed as a method of payment, then I expect a scenario where Bitcoin gains a small bridgehead in niche markets, which then slowly expands to some other markets.
Markets that suffer the largest burden of ID theft/chargeback fraud as a percentage of profit seem to be the most promising candidates for that bridgehead. An online merchant with a 4% net profit margin, who is also in a high risk market where they're losing 1% of revenue (i.e. 25% of profit) to fraud, might consider offering a 10% discount to customers who use Bitcoin, for example.
I'd guess the reasons that we don't see so this happening very often, so far, are: lack of familiarity with Bitcoin on the part of merchants, lack of sufficient volume to make it worthwhile to add a new payment method, and finally, some early adopters are still willing to spend bitcoins for ideological reasons or because they made an enormous profit by buying in early, so there's no need to offer those people an incentive.
Table of average net profit margin by industry, Retail (Internet) has an average 3.37% margin: http://pages.stern.nyu.edu/~adamodar/New_Home_Page/datafile/...