Software product line engineering offers developers a low-cost means to rapidly create diverse systems that share core assets. By modeling and managing variability developers can create reconfigurable software product families that can be specialised at design- or deployment-time. Service-orientation offers us an opportunity to extend this flexibility by creating dynamic product-lines. However, integrating service-orientation in product line engineering poses a number of challenges. These include difficulty in i) ensuring product specific service compositions with the right service quality levels at runtime, ii) maintaining system integrity with the dynamically composed services, and iii) evaluating actual service quality level and reflecting this information for future service selections. In this paper, we propose a negotiation framework that alleviates these difficulties by providing a means of achieving the dynamic flexibility of service-oriented systems, while ensuring the user-specific product needs can be also satisfied.