I got it working! 
But I'm afraid, I still don't know exactly what the problem was.
My solution was to move all the pin and interrupt initialization stuff from the constructor to an "init()" method. I basically renamed the constructor from
Code:
Encoder(uint8_t pin1, uint8_t pin2) {
pinMode(pin1, INPUT_PULLUP);
pinMode(pin2, INPUT_PULLUP);
encoder.pin1_register = PIN_TO_BASEREG(pin1);
...
to
Code:
void init(uint8_t pin1, uint8_t pin2) {
pinMode(pin1, INPUT_PULLUP);
pinMode(pin2, INPUT_PULLUP);
encoder.pin1_register = PIN_TO_BASEREG(pin1);
...
and called the init method in the setup() section:
Code:
#include <Encoder.h>
Encoder knob;
void setup() {
knob.init(24, 26);
}
...
That's definitely not the most elegant solution but at least it works...