I did a similar estimate using bunch of download sites and Google Keyword Tool/Trends. The hardest part, from my experience, is not the estimation of market size (people who need a product) but how many of them will actually turn into paying customers (people who want _your_ product).

Especially if your market has free alternatives.