In addition to Google Analytics, we tried Twitter, Facebook and Stumble Upon.

My feeling is that, at early stages, all outperform analytics unless you really know what you're selling and/or you've good landing pages. All have their specific "way to use it", e.g. on Facebook you need a page with engagement, on Stumble you need "something" that people can stumple upon :) e.g. blog posts.

Here I'm considering signups as conversions. Analytics (and Bing) were good to reach a lot of page views (that may still be useful).

for mobile applications Facebook Mobile Ads are pretty good since you can target very specific audiences and built local critical mass. whenever you're bidding on non-branded adword ads you usually have to compete with some incumbent that have spent time on their optimization which means you probably wont be able to beat them with your new product