I would really like to see approaches like these applied to movie scenes. Especially how differences in single colorized frames depicting the same scene could be handled.
They (I believe, although it might be the other guys) have a video up on YouTube demonstrating it on a Vietnam movie trailer. It looks appalling: aside from the usual averaged colors and saturation, the coloring is highly unstable and changes from second to second.
Found a video [1] colorized with the approach by these guys with the unstable coloring.
There are some other videos [2][3] colorized using differing approaches, that don't seem to have as much color unstability though the color in general appears more off.
Could of course also just be a property of the underlying source.
It seems like adding the colour would be the hard part. Once you had that, normalising the colour or smoothing it out across hundreds of similar images could be achieved by a second software algorithm.
Certainly colour correction, hue, contrast, brightness, would be easier to process than adding colour in the first place.