I am going with the multilayer approach. I have bumped against this “problem” myself now and again. Its of course not really something wrong, it just has to do with the “tolerance” settings of the magic wand selection tool. Your “black” lines have a grey edge due to a number of reasons not least of which is antialiasing. The magic wand tool is therfor only picking what is white, and the little line you are left with is actually very very light grey. You could try adjusting the tolerance so that the tool picks up more of the grey area at the boundary of your lines, although this of course means you will partially colour over the boundary of your lines.
There are a couple of ways i work with this. In the example you show the easiest way is to have the colour on a separate layer underneath which you can than quickly fill in the gaps with a brush (easy since the colour is on both sides of the line). Where you only have colour on one side, and therfore filling the missing gaps with paintbrush would take too long (you dont want to colour over the lines), i would also start with the colour on a new ayer underneath. I then ever so slightly blur this colour layer, duplicate it a few times and merge them together. Not saying this is the best method, but its just the way i have done it in the past without giving much thought to it.