PaulS:
The external interrupt pins are 2 and 3. They are NOT SCL/SDA.For two encoders, on 2 external interrupt pins each, you'll need a different Arduino. The Mega has 5 external interrupt pins.
Oh, I got them confused with the Leonardo, you are right.