the reason why you cannot paint back is because you might have used the simplest but not the best way of removing colour from the picture... you prob used the grascale function...
this is a different colour mode and when you try to paint colour onto a monotone image, ps gives you error message....
thus, once you have monotoned your picture, make sure that the mode is in either rgb colour mode or cmyk color mode...
Yes, agreed with showtime, you won't be able to use the history brush if you use the change colour mode function, or deleting colour channels method to get b/w. Try using the desaturate function, or monochrome in the channel mixer.
There are several ways of doing it tho.
My flow, not using the history brush,
1. From the layer menu, select Adjustment Layer, follow by Channel Mixer.
2. From the pop-up Channel Mixer dialog box, click on the Monochrom, somewhere at the bottom left of the dialog.
3. Click OK. Your image will go b/w.
4. In the adjustment layer, select the eraser tool and "brush" on the area that you want to be coloured.
You might also want to try adjusting the curves too, that'll bring out your colour contrast tremendously.
1. From the Layer Menu, select New Adjustment Layer, click on Curves.
2. In the Curves dialog box, pull the centre point of the curve vertically up, and the bottom left point of the curve horizontally right.
Your workflows were pretty cool...But how do you guys select the a particular portion of the photo (any tips on this) I find that the eraser tool is quite slow, that is it takes a considerable time to erase a particular area specially if it is an irregular shape. The magic tool should help make it fast but only if the shape is not irregular and has a good contrast else it is not accurate... How the experts here do select a particular area in a shortest time possible? ;p