Okay I think I found the answer. I have a note 3, but I hope that this solution will work across all Samsung phones.
1 - Go into S Voice and click settings
2 - (As others have suggested) - Scroll down to the 'wake up' category and make sure that the "Wake up Command" and "Voice Wake Up" options are selected
3 - Finally, click on the 'voice wake up' option. Not the slider bar...if you actually click on the 'voice wake up' text it will take you to another page with a check box (Wake up in secured lock). Check that box. Should work fine after that.
I don't know why Samsung designs the menu this way, it is kind of misleading. Hope this helps.