Here’s a really good post (with a flow chart!) in which Craig McMurty describes the steps and scenarios you should consider when making changes to your WCF contracts (service, message or data).