Protect Sheet / Workbook doesn't work for me?

those sheet and workbook protections are only for protecting from modification.  If you want to lock the whole workbook from open (or modification) that is done in the SAVE menu.  If you hit Save As and then you might need to click on the 'more options' to get the classical window (or just click F12).  There is a 'Tools' button / drop down next to the save.  In that you select General Options and then select the type of protection and the password:

Please note this protection is stronger than either the sheet or workbook protection (i.e. harder to crack) but I would still NOT consider this proper security for any truely sensitive information.  Treat all protections like those little luggage locks you put on the zippers, something to keep the casual nosey person out but will not stop someone who really wants to get in.