Hall sensor noise removal
It sounds like you need a debouncing circuit.
You can do it in code, but you are then trying to execute more code in you interrupt handler.
I would go for a hardware version.  I don't have the circuit to hand but if you search for a 'Schmidtt Trigger' based debouncing circuit.  You can implement it with 5 resistors, a capacitor, a LM386 OpAmp and a CMOS XOR IC (Inverts the signal which the inverting Schmidtt trigger inverts).

What happens is the Schmidtt trigger goes low when the input passes a certain voltage.  It remains low until the voltage passes the low voltage threshold at which point it goes high.  The CMOS XOR IC (I think its a 4004??) takes two inputs and inverts them.  It also adds extra hysteresis which further damps the bouncing. 

The values of your resistors affect the thresholds, but there are plenty of calculators on the web that will solve the values for you.

The LM386 has two channels and the CMOS usually has 4 so it becomes quite easy to debounce multiple signals.

Hope that helps.