It sound like you have too much code in your interrupt handlers or you are getting another Int0 interrupt before the Int0 handler returns. If the interrupt rate is in the millions per second you may need faster hardware. They do make quadrature counter chips.