What I do when this is necessary, is to stroke the text once in the first
color. Then select the new outlines, and (via the modify menu) do a "convert
lines to fills". Now you can stroke the first stroke because it's a 'fill'.

If the first stroke definately has to be lines, there are two ways around
this. First, you can delete the first stroke (the 'fill' stroke) after you've
made the second one, and then make it again. Or second, you can select all of
the second stroke, copy it, then hit 'undo' until the first stroke is a line
again, and then paste the second one back into the document.