yeah, which technically makes the non-compete invalid. They can't change the terms of your contract after you've already accepted the position.
What they're hoping for, is that you'll just bow down and take it, rather than pursue any other option, because you actually do want the job.
The next problem you run into, is if you do sign it, and then don't immediately start looking for another position, then they could argue back that you accepted the new terms of the agreement. In order to push the case that the non-compete is invalid, you have to immediately begin taking action in accordance with the idea that the non-compete is a deal-breaking change of your employment contract for you. If you continue working at the job for another 2 years, for example, you likely won't be able to convincingly make that case.
If you do leave the position, you likely have a case on your hands. In the event that they try to use the non-compete against you, you could claim the offer was invalid, because of the misrepresentation of your employment conditions, something you attempted to fix immediately upon starting the job (by attempting to leave again). This has been successfully argued in court before.
You may even be able to argue for damages, particularly if you moved across country, like you imply. It is grossly illegal for an employer to, for example, change your pay rate right after starting a new job, so you might be able to argue the same for an unexpected non-compete.
But obviously, I am not a lawyer. Everything I just said could be wrong, and you'd be crazy not to talk everything above through with one during the entire process.
But that's the general gist of how these things work.
Any company that does this is a very scummy company. Or they're just unorganized, and didn't think to send you all the paperwork before you started. I like chadash's suggestions above a lot.