What didn't work? A reed switch isn't going to respond if you ask it to switch too quickly. It's also not a very reliable solution. Still, the basic principle seems ok. Is the magnet close enough to the switch?
As you suggest, a Hall sensor is a better idea in the long run. You probably want one with a digital output, good rise/fall times, and unipolar switching. I've used a TLE4905 Hall sensor for speed sensing on an RC car (up to ~10,000 transitions/second), but there are plenty of other possibilities.