Need more info...
I'm still somewhat inexperienced in Excel but your question intrigued me because I thought that formatting sorted with the data. I tested this and the formatting sorts when I do it. My first question, then, is what formatting is applied to the data you are trying to sort? My second question is, what version of Excel are you using? I'm not familiar with the differences between Excel 2002 and other versions, but perhaps the version of Excel you're using doesn't support sorting formatting.