Depends on however that State resolves ties. I think most would make it be a matter of random chance, but frankly I doubt any tie after the initial result of a statewide election would still be a tie after a recount.
I agree, and the 2008 MN Sen race is a good example of the amount of swing that might be expected. MN has very good audit procedures for their elections, but even so there can be ballots in dispute. The initial count was Coleman leading Franken by 215 votes out of 2,885,555 cast. After the recount Franken led by 225 votes out of 2,887,337 cast. After the final court challenge the margin favored Franken by 312 votes out of 2,887,646 cast.
There are two factors to consider here. First is the change in the ballots cast. MN ended up with and additional 2091 ballots found to be valid. Missing votes and unreported or partial precincts can happen just due to human or technical errors. In this case it resulted in an additional 0.072% ballots cast which make up less than one in a thousand. However, when the margin is also less than one in a thousand, that matters.
The second is that the recovered ballots are unlikely to exactly mirror the statewide vote. That was true in MN where Franken gained 1,254 votes and Coleman gained 727. Statistical fluctuations can seem large because the added ballots are not uniformly distributed across the state. So in the case of a tie, it's very likely that a recount will find more valid votes, and it is highly unlikely that they will split exactly evenly when those added ballots total in the hundreds or thousands as they would for presidential electors.