Did a little poking around, looks like that's controlled by the style settings. Somehow your 'Normal' style got set to strikethrough text, which then applied itself to the row/column headers.
For 2003:
Go to Format>Style, select the 'Normal' style and click the modify button.
Change the formatting so strikethrough is not selected, then click OK.
For 2007:
On the Home ribbon, click 'Cell Styles,' right-click on the 'Normal' style and select Modify.
Click the Format button then remove the strikethrough with the options. Click OK.