In Firefox, all categories are left-justified - it looks fine. In IE, the "Movie Screencaps" category is pushed over to the right. The only difference this category has is that it has no immediate albums in it. Looking at the source, you see that this category has a class="catrow_noalb" compared to class="catrow" for the rest. In addition the empty cell to the left of this category (which holds the category thumbnail if you set one) has a align="left" tag compared to the rest not having one.
Looking at at the sample theme's style.css, "catrow_noalb" and "catrow" only differ in a color element, so that cannot explain it. So I assume IE has an issue with the align tag for the empty cell. Maybe it thinks if you want to align it, it should give it some space or something.
The easy fix would be to modify the variable $template_cat_list in themes/yourtheme/theme.php. If it's not present, copy it from themes/sample/theme.php or copy it from here. Modify as shown to remove the align="left" tag:
// HTML template for the category list
$template_cat_list = <<<EOT
<!-- BEGIN header -->
<tr>
<td class="tableh1" width="80%" align="left"><b>{CATEGORY}</b></td>
<td class="tableh1" width="10%" align="center"><b>{ALBUMS}</b></td>
<td class="tableh1" width="10%" align="center"><b>{PICTURES}</b></td>
</tr>
<!-- END header -->
<!-- BEGIN catrow_noalb -->
<tr>
<td class="catrow_noalb" colspan="3"><table border="0"><tr><td>{CAT_THUMB}</td><td align="left"><span class="catlink"><b>{CAT_TITLE}</b></span>{CAT_DESC}</td></tr></table></td>
</tr>
<!-- END catrow_noalb -->
<!-- BEGIN catrow -->
<tr>
<td class="catrow" align="left"><table border="0"><tr><td>{CAT_THUMB}</td><td><span class="catlink"><b>{CAT_TITLE}</b></span>{CAT_DESC}</td></tr></table></td>
<td class="catrow" align="center">{ALB_COUNT}</td>
<td class="catrow" align="center">{PIC_COUNT}</td>
</tr>
<tr>
<td class="tableb" colspan="3">{CAT_ALBUMS}</td>
</tr>
<!-- END catrow -->
<!-- BEGIN footer -->
<tr>
<td colspan="3" class="tableh1" align="center"><span class="statlink"><b>{STATISTICS}</b></span></td>
</tr>
<!-- END footer -->
<!-- BEGIN spacer -->
<img src="images/spacer.gif" width="1" height="7" border="" alt="" /><br />
<!-- END spacer -->
EOT;