It might be a problem with the GPS TX cable or with something in the software. Does anyone have any suggestions?
Or, it might be that you don't have it connected to your Mega correctly, or it could be that you haven't shared YOUR code.
Post some pictures and code.