The Shadow Catcher shader is designed to return the whole appearance of the shader in the Alpha channel. You can see this when rendering a shadow catching object, and switching the display from RGBA to RGB (discarding the Alpha channel information):
normal RGBA display mode:

only RGB channels, entirely black:

only Alpha channel:

Now to add color to your shadows, You'll need to work on the RGB components, as the Alpha is just a blending factor between foreground and background. You can use a very simplified setup like this to get started:

So I'm feeding the Alpha Channel of my shadow catcher layer into a set alpha node, which allows me to define completely different RGB components there. In this setup, I went for a cheap and simple solid dark blue color, but it could also be your color corrected background image with a bluish tint in there.
further examination
For further explanation and the Render Layer setup, check out the .blend file here:

EDIT: Comping over a background image
The following setup should give a hint on how to tint the shadow, in case you need to comp it over an arbitrary background. I forgot that in the original answer, apologies here. Check the updated .blend file from here:

As troy_s suggests in the comments, to tint that shadow on the background, a multiplication has to happen first. Think of the Alpha channel as a constriction of light: It's like cutting out a FG image, and thus it merely defines a geometry rather than a transparency. That can be utilized here. The node setup basically multiplies the BG image with the desired tint color:

Multiplying is one way to treat that BG, but you can use other grade nodes if you like. In that first section you basically tint the whole background before assigning the Alpha channel to that resulting image. So in essence, you grade the BG, and then cut out the portion which is in shadow, and comp that over the original background. An additional Alpha Convert is needed here. If you mute it, you'll notice a lift of pixel values in areas where there should not be any change. The Alpha Convert fixes that.
The resulting image shows a comparison between the two (black and tinted). Please note that the tinted shadow will always get lighter than the black one. That's simply because nothing can become darker than (0.0, 0.0, 0.0)
. To achieve a different color (like blue), channels need to be lifted.
