No "Sort Layers By Depth", no one ever said anything about that. If you can't follow these very clear instructions, you may just be hopeless.
1. Take all of the layers you may wish to animate the sorting order of and place them in a single group or bone layer (both of these are 'grouping' layers).
2. Open the layer setting dialog of the group or bone layer you just put all of these layers you wish to sort into.
3. Select the depth sort tab.
4. Check only the "Enable animated layer order" check box. Checking "Sort layers by depth" will gray this option out and will not allow you to animate sorting layers in the layers window.
5. Select any frame other than zero.
6. Now, in the layers window, move one of the layers in that grouping layer (remember, either a bone or group layer, your choice) to somewhere else in that grouping layer.
7. Select the grouping layer and you will now see a keyframe at that frame.
TaDa!