There has been extensive research on finding distance measures between individual colors which conform to the human visual system color perception. With the recent advent of using and naming color combinations by abstract concepts (classic, romantic), this paper addresses the new problem of computing distances between such combinations, which are referred to as color schemes. In addition, the paper proposes an algorithm to compute the distance measure which is shown to be competitive compared to various state of the art distance measures adapted to the problem at hand. In particular, the proposed distance measure, referred to as the Color-based Earth Mover's Distance (CEMD) embeds the CIEDE2000 color difference formula into the Earth Mover's Distance (EMD). The CEMD performance in computing distances is evaluated through a color scheme retrieval framework. Quantitatively, it is shown that the CEMD provides in general the highest precision at K as compared with the EMD and a distance based on Fisher Vector representations of color schemes, which we refer to as FD. Qualitatively, it is shown that retrieved color schemes are more similar to the query scheme when the CEMD is employed as compared with the EMD and FD. Qualitative results on image ranking by concept using the CEMD are shown to be better than those obtained using tags.