In this paper, we present the "Slow Start Problem" in participatory sensing applications where a service is provided based on data collected by participants. The slow start problem refers to the initial stage in participatory sensing service deployment, during which service adoption remains sparse and, hence, the collected data does not offer adequate coverage. Predictive models, learned from data, offer a way to generalize from sparse observations, but the models themselves need to be statistically reliable to offer a reliable service. To achieve service reliability, this paper offers a modeling approach, where simpler models are used initially, gradually transitioning to more elaborate models, when enough data is collected. A key challenge and contribution of the work is to time model transitions correctly to provide theoretical guarantees on modeling error. Our technique takes a holistic approach in bounding modeling error as opposed to prior statistical approaches that bound the error of a single model component at a time. This technique is tested in the context of a vehicular participatory sensing application, called GreenGPS, where participant data is used to build models that predict fuel consumption of vehicles on different routes for the purposes of choosing the most fuel-efficient route for each vehicle (as opposed to the shortest or fastest). We show that our approach significantly reduces prediction error in the initial stages of deployment.