I'd go paid from the get-go. In my experience, once users associate something with "free," it's much harder to get them to pay anything for a similar product.