After more testing, I've found that my sensor works great as long as the RPM stays under 15000 or so. I'm going to agree with you jremington that the spikes for higher RPMs cause too much noise in the circuit/Arduino.
wvmarle:
Try cleaning up your signal further and insulating the Arduino better from the nasty spark plug spikes and other noise: place an optocoupler between your 555's output and the Arduino, thereby completely separating the two circuits. So NO connected grounds or anything.
I checked the original source of the circuit I'm using and there was a brief mention of an optocoupler, I'll check into that.
Hmm, I think the only grounding point available is the battery. The sensor will be used on a weed whacker while it's running, so I can't have wires going off somewhere to physical ground.
Since I've found that my sensor works for sub 15000 RPM, I think I'll just adjust what I'm doing to fit that constraint. If anyone has any more suggestions please reply. This is my first big electrical project and it's teaching me there's alot I don't know 