Format->cells->date Not Applied

I can select an individual cell or range, select Format->Cells->" date" format, hit okay, and nothing actually changes unless I click on a cell so that it brings up the edit cursor. I can then hit enter (not changing the content of the cell in any way) and then Excel recognizes it as a date. The cell values are all in the standard "3/14/2001" format, with the exception that single digits are 0-padded, and there are no spaces preceding or following the date string. The issue here is that without the cells being recognized as actual dates, they cannot be properly sorted, eg: the original range:

01/04/2005
01/01/2005
01/02/2004
01/03/2005

is sorted, incorrectly, to:

01/01/2005
01/02/2004
01/03/2005
01/04/2005

...obviously for ascending order, the single 2004 date should be placed at top. Any ideas other than a custom date-text parsing macro? I could do that, but the size of each sheet, the number of sheets per batch, and the frequency of individual batches makes that idea completely impractical. ...Technically, my macro couldn't sort the above ranges correctly, but on further investigation, I noticed I couldn't do it manually either.