I think the one legion is by far the bigger problem. If you have an early discovery of the Americas and a rweason to go, ancient technology is up to the challenge (albeit not on the scale of the 1600s, which limits your reasons). Play the usual 'germs' part and you have fairly empty lands that invite Romanised settlers with a taste for extensive agriculture and transhumance.
The problem is, the Roman state didn't really go in for long-range colonisation. The historical models this would like run off of are the Roman expatriate communities in India and the client kingdoms of the Arabian Peninsula. I can't see any reason why the army would possibly want to go there. Since a legio requires the authority of dilectus (invested in the senate and its magistrates), whatever military forces the locals will develop are not going to qualify.