Protection only protects "locked" cells. By default, all cells are locked.
To unlock them, make sure your sheet is unprotected, highlight the cells you want unprotected, and go to Format | Cells | Proection and uncheck the "Locked" radio button. Then Protect your sheet.