Why is my interrupt code not working?
Only some ports on the Atmega2560 support pin-change interrupts, specifically ports B, E (bit 0), J (bits 0 to 6) and K.

Looking at the reference schematic that means that these pins on the board are supported:

     Chip
Name  Pin  Pin on board
-----------------------

Port B

PB0 - 19 - D53 (SS)
PB1 - 20 - D52 (SCK)
PB2 - 21 - D51 (MOSI)
PB3 - 22 - D50 (MISO)
PB4 - 23 - D10 
PB5 - 24 - D11
PB6 - 25 - D12
PB7 - 26 - D13

Port E

PE0 - 2 - D0 (RXD0)

Port J

PJ0 - 63 - D15 (RXD3)
PJ1 - 64 - D14 (TXD3)
PJ2 to PJ6 - not connected on board

Port K

PK0 - PK7 - (89 - 82)  - A8 - A15


Thus you can see that D10 to D12, which you say works, are in that list. Other random ones would not be.



SoftwareSerial

You can see confirmation on the page for SoftwareSerial where it says:


  Not all pins on the Mega and Mega 2560 support change interrupts, so only the following can be used for RX: 10, 11, 12, 13, 14, 15, 50, 51, 52, 53, A8 (62), A9 (63), A10 (64), A11 (65), A12 (66), A13 (67), A14 (68), A15 (69). 


This is because SoftwareSerial uses pin-change interrupts to detect incoming serial data, and thus the disclaimer on that page about which pins it will work with.



Atmega2560 pin-outs






  PinchangeInt should work on any digital pin


Note that the Atmega328P (as used in the Uno) has less ports, and all are available for pin-change interrupts on that board.