The code I use "test_with_gps_device.ino" from "TinyGPS".
That doesn't help. Post the code you are using, or at least a link to where you got it.
I use pin 2(rx) and pin 3(tx), (I use my Tektronix 2235 oscilloscope to check).
Does that mean you are using SoftwareSerial?
http://arduino.cc/en/Reference/SoftwareSerialNot all pins on the Mega and Mega 2560 support change interrupts, so only the following can be used for RX: 10, 11, 12, 13, 50, 51, 52, 53, 62, 63, 64, 65, 66, 67, 68, 69
If you are, then I suggest you change the sketch when you use it on the Mega, to use one of its other hardware serial ports.