I'm working with Excel 2003, but this functionality should be in Excel 2002 as well. If you can allow the user to select locked and unlocked cells, and to format rows and columns, then the user may hide/unhide columns/rows.
I know that this isn't much help, but it is an idea. Perhaps you don't want the user to select any cells or format rows and columns. While the worksheet is protected, they at least cannot edit the data.