We study a solution approach for a staffing problem in multi-skill call centers. The objective is to find a minimal-cost staffing solution while meeting a target level for the quality of service to customers. We consider a common situation in which the arrival rates are unobserved random variables for which preliminary forecasts are available in a first stage when making the initial staffing decision. In a second stage, more accurate forecasts are obtained and the staffing may have to be modified at a cost, to meet the constraints. This leads to a challenging two-stage stochastic optimization problem in which the quantities involved in the (nonlinear) constraints can only be estimated via simulation, so several independent simulations are required for each first-level scenario. We propose a solution approach that combines sample average approximation with a decomposition method. We provide numerical illustrations to show the practical efficiency of our approach. The proposed method could be adapted to several other staffing problems with uncertain demand, e.g., in retail stores, restaurants, healthcare facilities, and other types of service systems.