Mit dem Atmega 2560 habe ich noch nicht gearbeitet, jedoch bei den anderen mit denen ich gearbeitet habe habe ich noch nie solche Probleme gehabt.
Prellen hast du eigentlich nur bei mechanischen Schaltern. Du verwendest vermutlich eine Lichtschranke, dort gibt es soetwas nicht. Was ich mir nur vorstellen könnte ist das die Räder ganz leicht hin und her bewegen und somit die Lichtschranke ständig schaltet.

Du könntest noch versuchen eine direkte Verbindung zwischen INT Eingang und Masse machen (direkt am arduino). Dann hast du auch ausgeschlossen das du dir Störungen über die signalleitungen einfängst.

Du könntest auch eine Led am Eingang anschließen (eine superhelle wäre von Vorteil) . Wenn es flackert oder blinkt schaltet der INT.

MfG Hannes