GradientChecking, can I blame float precision?
The fact that there is a sweet spot is a common issue in numerical differentiation. The issue is that using a high epsilon value will give you high error due to the fact that the numerical derivatives have error $O(\epsilon)$ (or $O(\epsilon^2)$ if you use centered difference), and using a very low epsilon will result in cancelling errors (see catastrophic cancellation question) due to the fact that you are substracting two numbers that are very close. It seems that $\epsilon = 0.01$ is a fair trade-off between these two extreme situations in your case.