Just to close the loop here, I had a private conversation with James and it turns out there is a subtle bug in the implementation of the gradient checking formulas. Look carefully at the denominator in this expression:
diff = \displaystyle \frac {||grad - gradapprox||}{||grad|| + ||gradapprox||}
It turns out that you get something very close to the correct answer if you do this instead:
diff = \displaystyle \frac {||grad - gradapprox||}{2 * ||grad|| }