Did you unlock these other cells before protecting the sheet?

By default all cells are locked, so when you protect the sheet without changing formatting, you can't change anything on this sheet. Likely your course of action must be:

1. Unprotect the worksheet (in case it is protected currently);

2. Select entire worksheet (click on rectangle at top left on sheet);

3. Set all cells on worksheet unprotected (Format Cells: uncheck Locked);

4. Select cell/range of cells you want to restrict user changes for;

5. Set cell/range of cells protected (Format Cells: check Locked);

6. Repeat 5. - 6. until you have set protection for all cells you need to be protected;

7. Protect the worksheet.

In case you need to change previously formatted locking on worksheet, where you want most of worksheet locked, and only some cells unlocked, the order of seting Locked/Unlocked will be reverse.