I had a similar issue when I had my Galaxy Nexus. I had to take to Sprint to let them load it. Not sure why it did that but what every they did they fixed it.
How would I flash it myself? I'm new to the Android phones. Is there a program I can download to do this? Can I go straight to 4.3 or do I have to go one by one with the updates?
Is the phone rooted? If you don't know, ask the person you bought it from. A rooted phone may prevent an OTA update depending on whether any key files have been changed.