Thought of one thing that might contribute to its difficulty as it is today. If you are trying to jump away there is no forgiveness if you don't reach the wall. That is, you can be 4 frames early with a jump press, but if you are early with a direction change and you reach the wall more than 4 frames later, or don't reach, you will fail.
Update: Wall jump also doesn't give you any acceleration away from the wall (push off). I think this may make vertical climbing easier and an away kick more difficult.
Again, I really appreciate your feedback!