O problema não é na biblioteca, mas numa diferença que existe entre o Arduino UNO e o Mega que limita em que pinos NewSoftSerial pode receber dados. Segudo o que é explicado neste fórum, esses pinos são:
10, 11, 12, 13,
50, 51, 52, 53,
62, 63, 64, 65, 66, 67, 68, 69
Mas a biblioteca pode transmitir em qualquer pino.
Como a maioria esmagadora dos exemplos que usam NewsoftSerial foram feitos para o UNO (quem usa Mega geralmente não precisa de portas virtuais), é quase certo que usem os pinos abaixo de 10 e assim não vão funcionar no Mega. Isso inclui exemplos de uso para GPS, GPRS, bluetooth…
Se você tem um Mega e não precisa de mais que as quatro portas seriais físicas, eu recomendo que você modifique os exemplos para que usem as portas físicas e não a biblioteca NewSoftSerial (comece apagando a linha #include <SoftwareSerial.h>). Isso economizará espaço na sua flash e dará mais velocidade ao seu programa, porque a criação e uso de uma porta serial virtual tem um impacto no processamento.
[…] exemplo que você pegar na internet que use a biblioteca Newsoftserial poderá não funcionar no Mega. Nesse modelo de arduino, use as portas seriais […]