1) Partner with TangibleCryptography, Bitinstant or another one of these cash deposit direct to bitcoin outlets.
2) Ask them to issue a coupon code for your store (say $100 off $1000). Coupons go to people who purchase $1000 worth of btc from them and who are first-time customers (I assume they do KYC to check this).
3) Eliminate coupon code sharing by requiring that the bitcoins used to make the purchase match the bitcoins purchased from the cash to bitcoin outlet
4) Identify a few popular items that you can offer competitive prices for.
5) Post the item and detailed bitcoin purchase, download, and coupon acquisition instructions on "slickdeals.net" Also post a price comparison vs. Amazon, newegg, etc.
Expect to lose some money off this. The goal is to get name recognition for the bitcoinstore + bitcoin acquisition methods in a very widely used deal forum.
Ideally you can get the absolute cheapskates who populate slickdeals.net to regularly scan your site for new offers and post about them autonomously.
Presumably the name recognition will help your partner as well.
[I don't think you should do this until the site has been substantially upgraded. It looks a bit like a low-price scam site right now. (I mean that in the nicest possible way.)
Scam sites often involve purchasing hardware from foreign companies. These companies also ask for wire transfer, etc. less reversible methods of payment than credit cards.
Thus you have to improve your image]
So we are using coin taint to attempt to track customer discounts across multiple merchants? I suspect this will lead to all sorts of customer complaints and ruin the reputation of all the merchants involved rather than generate sales. Anyone actually consider a high degree of privacy to be a useful feature of Bitcoin?