Select the cells you want users to be able to use and then make sure they are not locked before you protect the sheet. It's in the format of the cells under the protection tab (Excel 2003).
Once you've cleared the tickbox, you can then protect the sheet as normal.