We address the issue of failure in service compositions. Such failures occur when a service in the composition evolves or becomes unavailable. Our goal is to analyze these failures and recommend possible service repairs. We begin with a formal model of services and service compositions. In this model, services are abstracted as functions that map input domains to output domains and knowledge of their semantics is restricted to a relatively short table of input-output pairs. Service compositions are then formed with the help of two functional operators. We then design a technique to support programmers in debugging service failure by offering a ranked list of suggested repairs. The repairs may substitute the failed component service or any portion of the composition that contains it. Finally, we describe experiments that validate our technique.