I realise that I'm coming to this thread a bit late, but have you thought of not using interrupts, and having a bit of hardware that looks at the wheel sensors and outputs logic 1 when the wheel is not spinning, and 0 when it is.
You could use a counter that is reset by the wheel sensor. If the counter MSB becomes set, then the wheel is not spinning. Obviously you need to have a suitable choice of clock frequency for the counter. Your software then becomes drastically simpler - just poll the 4 inputs, and if the pin goes high, back off on the brakes for that wheel. You could even do it all in hardware (heaven forbid!)

Best of luck