It does appear red on Firefox and IE 8. But perhaps you need to change the border-style too.
.field_set{
border-color: #F00;
border-style: solid;
}<fieldset class="field_set">
<legend>box</legend>
<table width="100%" border="0" cellspacing="0" cellpadding="0">
<tr>
<td> </td>
</tr>
</table>
</fieldset>