After some more thoughts, I have decided to do the Encoders in a FPGA, mainly because I will need interrupts in other parts of the program as well and also think that it will get too slow for what I want to achieve.
Papilio has some boards and I got both the 250K and 500K in my hands 
Interesting thing is that you can program it using the Arduino IDE.
Here is a link to a pretty good summary about quadrature encoders
Cheers