Well first question I would ask is what two arduino pins numbers are you wiring your encoder channels to. And while I know you said you are running the example sketches, you really should post a copy of the exact sketch you are running that doesn't work correctly. Copy it from your IDE sketch editor and past it here in a code (#) window.
Lefty