It sounds like you're using a table and have applied a table style. You need to convert the table to a range, then convert it back. Do the following:
- Select a cell in the the table, then under the 'Table Tools' > 'Design' tab, select Convert to Range. Select yes at the pop-up asking whether you'd like to convert it to a normal range.
- Highlight the whole table again, the under the 'Insert' tab, select table. Click on ok in the pop-up window.
The formatting should remain consistent now when you're sort the data.