How to read clock input on an arduino
Why don't you try improving your code efficiency? Increasing your baud rate for your serial will really help. Just change it to Serial.begin(115200);. Then use Serial.print() less often. If all that fails, this page is fantastic: http://playground.arduino.cc/Main/RotaryEncoders