Вы на правильном пути, создав собственный скин. Просто скопируйте CheckBoxSkin по умолчанию и добавьте Rect на верхнем уровне, чтобы он рисовался первым (ниже, где объявлены состояния и перед первой группой):
<s:Rect left="0" right="0" top="0" bottom="0">
<s:stroke>
<s:SolidColorStroke color="#ff0000"/>
</s:stroke>
</s:Rect>
Затем установите новый скин в качестве обложки для флажка, либо в CSS, либо непосредственно на конкретный флажок через его skinClass.
Надеюсь, это поможет.