Martik - Are you testing the prox (actually a Hall effect sensor, not strictly a "proximity" sensor) "by hand" on the bench, or with the magnet mounted on the actual shaft and rotating at realistic speeds? This might make a difference, because rate-of-change may be what the sensor is most sensitive to. You might also want to try with a different magnet. A nice size rare earth magnet to use would be ¼" or 5/16' diameter and ⅛" thick. The magnet pictured in the listing looks like it's only about 1 mm thick. Range of the Hall effect sensor does depend on the strength of the magnetic field.
Of course, you do have the remedy of returning it. Amazon is pretty good about that, and if you can't get it to work, you definitely have justification.
I used to use lots of prox and other sensors in the equipment I designed and built while at HP. Bought one of those tachometers a couple years ago, but wired it to a reflective fiber optic photosensor. Didn't have a good way to mount the supplied sensor.