Protocols governing communication among system components evolve during design and maintenance and need to be re-tested. For faster testing turnaround time, it is important that the consistency of the testing infrastructure with the protocol be preserved across changes. In this paper, we propose a state exploration based approach to identify the impacts of protocol changes on a given set of protocol tests. Protocols are modeled as a network of communicating finite state machines exchanging messages over bounded queues. Each machine denotes the behavior of an individual protocol component (controller). A protocol test is modeled as a sequence of inputs from the environment to the protocol controllers in an execution starting from a stable protocol state. A notion of consistency of a test relative to a protocol is introduced. Conditions under which a protocol change requires changing a test to preserve the consistency of the test are identified. Changes consisting of multiple atomic updates are analyzed to remove redundancies and their impact on tests is studied. A by-product of the proposed approach is a classification of tests based on how they are impacted by protocol changes, which can help users in regression test selection.