System Software Not Authorized by Verizon Wireless?

I have a Samsung Galaxy Mega 2. I was upgrading, so I did a factory reset, in order to sell it. After the reset, it booted up to the error message: System software not authorized by Verizon Wireless has been found on your phone. Please turn off your phone and go to the nearest Verizon Wireless store for help.
A couple things:
1. It was never a Verizon phone. IT was AT&T before I had it, and it was on Straight Talk while I used it.
2. I have never tried to root or modify this phone in any way, shape or form.
I aprreciate any help! Would love to be able to fix it.