That's not a strong argument either. You could substitute "contract" with anything. I say this as a staunch libertarian. Government restrictions aren't bad because "government", but because restrictions.
The free market works best when government restricts the freedom to restrict freedom. That's why cartels being illegal is good (they restrict competition), bans on insider trading are good (they restrict fair competition), etc. Non-compete restricts the freedom on the labor markets.
If you let people do anything they want because freedom, you don't actually get freedom.