If my past experience with the labels and intuition is correct, the labels were protesting because they wanted Apple's paid service to roll out first, perhaps had even given Apple assurances that they'd be first (related to the ~$150M upfront?). This would also explain why reports were that they were dragging their feet in negotiations with others, and why Amazon and Google may have chosen to go without. People selling digital music are very sensitive to the early mover advantage iTunes brought Apple.