How do I recolor an image? (see images)

Easiest would be to use ColorMatrix for processing images, you will even be able to process on fly preview of desired effect - this is how many color filters are made in graphic editing applications. Here and here you can find introductions to color effects using Colormatrix in C#. By using ColorMatrix you can make colorizing filter like you want, as well as sepia, black/white, invert, range, luminosity, contrast, brightness, levels (by multi-pass) etc.

EDIT: Here is example (update - fixed color matrix to shift darker values into blue instead of previous zeroing other than blue parts - and - added 0.5f to blue because on picture above black is changed into 50% blue):

var cm = new ColorMatrix(new float[][]
{
  new float[] {1, 0, 0, 0, 0},
  new float[] {0, 1, 1, 0, 0},
  new float[] {0, 0, 1, 0, 0},
  new float[] {0, 0, 0, 1, 0},
  new float[] {0, 0, 0.5f, 0, 1}
});

var img = Image.FromFile("C:\\img.png");
var ia = new ImageAttributes();
ia.SetColorMatrix(cm);

var bmp = new Bitmap(img.Width, img.Height);
var gfx = Graphics.FromImage(bmp);
var rect = new Rectangle(0, 0, img.Width, img.Height);

gfx.DrawImage(img, rect, 0, 0, img.Width, img.Height, GraphicsUnit.Pixel, ia);

bmp.Save("C:\\processed.png", ImageFormat.Png);

It also depends on what you want: do you want to keep the original and only adjust the way it is shown? An effect or pixelshader in WPF might do the trick and be very fast.