Don't do a Serial.print() inside an ISR. If it does work, consider yourself lucky and stop doing it as soon as possible because things are (were?) problematic when printing from an ISR (but supposedly fixed in IDE 1.5; see Fix lockup when writing to HardwareSerial with interrupts disabled · matthijskooijman/Arduino@eb86af7 · GitHub ).
Regarding the rest of your question, you stated that you tried the PinChangeInt library and it didn't work for you. This thread is about the PinChangeInt library. The code you speak of was written by someone else so I don't think this is the appropriate place for this question, but perhaps someone will lend you the time and help you out.