Encoder too fast for a poor Atmega328?
I have run your code through avr-gcc with -Os optimization (YMMV if you use different compiler, flags etc., but in could be good starting point) and disassembled result, here is it:

00000090 &lt;__vector_1&gt;:
 2  90: 1f 92           push    r1
 2  92: 0f 92           push    r0
 1  94: 0f b6           in  r0, 0x3f    ; 63
 2  96: 0f 92           push    r0
 1  98: 11 24           eor r1, r1
 2  9a: 8f 93           push    r24
 2  9c: 9f 93           push    r25
1 2 9e: 4c 9b           sbis    0x09, 4 ; 9
2 . a0: 06 c0           rjmp    .+12        ; 0xae &lt;__vector_1+0x1e&gt;
. 2 a2: 80 91 00 01     lds r24, 0x0100
. 2 a6: 90 91 01 01     lds r25, 0x0101
. 2 aa: 01 96           adiw    r24, 0x01   ; 1
. 2 ac: 05 c0           rjmp    .+10        ; 0xb8 &lt;__vector_1+0x28&gt;
2 . ae: 80 91 00 01     lds r24, 0x0100
2 . b2: 90 91 01 01     lds r25, 0x0101
2 . b6: 01 97           sbiw    r24, 0x01   ; 1
 2  b8: 90 93 01 01     sts 0x0101, r25
 2  bc: 80 93 00 01     sts 0x0100, r24
 1  c0: 81 e0           ldi r24, 0x01   ; 1
 1  c2: 8c bb           out 0x1c, r24   ; 28
 2  c4: 9f 91           pop r25
 2  c6: 8f 91           pop r24
 2  c8: 0f 90           pop r0
 1  ca: 0f be           out 0x3f, r0    ; 63
 2  cc: 0f 90           pop r0
 2  ce: 1f 90           pop r1
 4  d0: 18 95           reti


Numbers before instruction addresses is my addition to disassembler output, number of cycles for execution based on AVR Instruction Set Manual. If I am counting it correctly, it is 43 cycles in total + 5 cycles for interrupt response (+ about 3 cycles for pin change to propagate). The ISR code can be hand-optimized into much shorter if necessary. But it even so it is about 50 cycles, 3 us @ 16 MHz.

PIND is read 12 cycles after ISR start, about 20 cycles (1.25 us) after INT0 edge. Should be still OK.

You do not have much marginal, but it should work. OTOH any other ISR will probably "kill" it as ATmega does not have interrupt controller with priority handling. Btw. in the code you put here, there is no processing of count variable, so even for test it need to be more complicated. Are you sure, you are not doing anything affecting ISR latency there?

As an alternative solution -- if you can consider XMega for your project (assuming you want to use AVR), these have hardware support for encoder and you can drive counter by it without need for FW interaction.