I have this problem too. No layers are locked, many hidden, and this option is grayed out. Selecting layers doesn't help either.
I can do it no problem in a new document but not in the one I need it for which has dozens of layers and folders.
Update: When I tried to unlock all layers using "layer > lock layers" it ignores folders that are locked. Manually unlocking that folder fixed the issue.
If the hidden layers are within visible groups they can't be deleted with the delete hidden layers command.
That does not seem to be the case – deleting hidden layers from visible Groups with »Delete Hidden Layers« works fine for me.