I was one of the founders of itsadeal.com.au, we've since stopped about 6 months ago to pursue other ventures. I would strongly advise against a newspaper ad, we went down this path and for $500, this got us about 5 subscribers. Google ads work, but remember to tie them into something you can make money off. It's not smart to compete using keywords such as "daily deals" unless you have a sizeable budget. A better approach is to customize ads which sell your products and if you have something with a large margin you should be able to come out on top (more effort, but much better ROI).

That's why you don't have a lot of sales then.

I wouldn't be rushing to spend big on ads until the site was settled and smooth. If you can get a few niche products running at once and get some ads promoting that field, you might have some luck.