Creating a versioning scheme for web services is a challenge that I have faced on a few occasions before. My experience is that creating compatible versions of a web service takes a lot of consideration, and I have not really found any good approach. The article ‘A Theory of Compatible Versions‘ gives a very good foundation for making compatible versions of an XML document, which can be used as a foundation for making compatible web services.
I think compatibility underlines the fact that a web services interface needs to be carefully designed, for instance using the contract first approach. You cannot simply have your WSDL file generated from existing code and publish it.