Udi Dahan writes about "Contract First, Discussion Second?" saying that "a service's contract is a more "take-it, or leave-it" kind of deal." 

There are situations when this is true - for example when Amazon decided to expose some of its functionality as Services they probably didn't negotiate it with most (if not all) of us. Similarly, whenever you want to consume a deployed version of a service you can either use it as is or move on.

However, services are rarely developed in a void. This means that when you set up to design the next iteration of a service (first or otherwise) there are usually several potential consumers out there (other internal systems, partners etc.) - and like it or no, you will be negotiating the service contract with them, after all, the  whole idea of the service is to add some business value. If you disregard your consumers, it will make it harder on them to actually make use of the (hopefully) wonderful functionality you will be providing.

This, Also means that it is better to negotiate the contract first (i.e. as one of the first steps of  developing the next service version). Again, deciding on the contract upfront, allows the other parties to get organize to better take use of the functionality that will be exposed through the service once it is deployed.

I suggest you be pragmatic when you set up to develop a service, meet with the potential consumers and try to agree on something that will be useful for them - or as the Beatles once said "let it be, let it be, speaking words of WSDL, let it be"…