Tenes otra maquina para probarlo? O bien colgarlo en algún lado con una tabla de ejemplo así te digo si a mi me funciona...puede que IE te este dando problemas solo a vos, o puede que no, pero primero descartaría que no sea tu PC.
Con ese ejemplo también te da error? Si pones algo como:
Código PHP:
<?
// Enviamos los encabezados de hoja de calculo
header("Content-Disposition: attachment; filename=excel.xls");
header("Content-type: application/vnd.ms-excel");
echo '<table border="1" >
<tr>
<td>Test</td>
</tr>
</table>
';
?>
te hace lo mismo?