When you protect a worksheet from the user interface it's displayed a little window where you can set a password and below this text box there're a lot of options.
By default only the 2 first are set on: Select locked cells and Select unlocked cells. All other options are disabled. Number 12 (in 2010 version) is Use autofilter. Try checking this at protection time, if it's yet protected and you don't know the password you can't change this parameter.