Recommender systems have been successfully used to address the problem of information overload, where consumers of goods and services have too many choices and overwhelming amount of information about each choice. Here we focus on service recommendation and demonstrate the need for using multiple criteria regarding service qualities, and the need to consider multiple contextual dimensions regarding the expected use of that service. These two requirements are not considered together by existing service recommenders systems, motivating our work on an approach which unifies both. To make such an approach precise and effective in situations of sparse feedback, we need a reliable scalar measure for context similarity when dealing with categorical context dimensions. This need underpins the main contribution of this paper - demonstrating that concept abduction provides such a reliable measure for context similarity when the categories of a context dimension are defined as concepts in an ontology. We position this contribution within a proposed multi-context and multi-criteria approach for service recommendation based on collaborative filtering. Using experiments over a real-world dataset, we demonstrate how the concept abduction-based context similarity measure can be used to address the sparsity of data within a single context segment by allowing us to use rankings from context segments nearby.