It is wired as they suggest in the datasheet with a 100pF capacitor across ground and supply.
not 100pF, 100nf, change immediately


When I flick the engine over by hand, it reads as it should, but as soon as I start the engine, there is another problem.
= noise pick up

For some reason the LCD basically just turns off, or the display goes extremely dull and it stops reading the RPM.
have you checked if the sensor "suck" the power supply when generating rapid pulses? what do you use for power supply?

Does the hall sensor that I am using seem suitable for the application? The reason I ask, is because I honestly had no idea about them, so I briefly looked at the datasheets and then selected one from the list...
the only problem with the sensor is that it has single ended output which makes it much more difficult to fight noise pick-up

firsts:
1) use a sturdy power supply
2) set the load resistor for the sensor to minimom (20ma max @5V) stay a bit conservative and use 330 ohms. The lower this resistor, the more power the induced noise need to have.
3) put 100nf at Vcc at the sensor and also at the point where the cable connect to Vcc
4) use a shielded cable grounded ONLY at the uc box
5) put the uC and associated circuits in a steel box.
6) read http://www.8052.com/faq.phtml?FAQ=84


Erik