The solution was unprotecting the worksheet before changing the underline property. Excel 2003 has a new way of locking cells, and the cell was locked both from changing the content and changing the format. A different way of fixing it is to just lock the cells from changes in the GUI, which allows changes to still be made from the code.