As discussed in this article, it is well established that a conviction can be nullified if the testimony that it is based on is known by the prosecution to be false. The requirements imposed w.r.t. prosecution knowledge are not easy to satisfy. There is no evidence that the prosecution knew that the testimony was in part false, nor that it was material. Materiality is relevant, see US v. Bagley, which holds that
the prosecutor's failure to disclose evidence that could have been
used effectively to impeach important Government witnesses requires
automatic reversal. Such nondisclosure constitutes constitutional
error and requires reversal of the conviction only if the evidence is
material in the sense that its suppression might have affected the
outcome of the trial.
As for prosecution for perjury, he can maybe be prosecuted for perjury, though given the facts in evidence he will not be convicted (so the answer about prosecution depends on how the gaps are filled in). Perjury statutes have three essential elements. First, the statement must be false – that much could be true, depending on what he said. If he said "I was watching America's Funniest Cat Videos at the time when Smith entered", and the other video showed that he was watching WTF Smackdown, the testimony would be false. If he said "I had been watching America's Funniest Cat Videos at the time when Smith entered", then the statement is false if he had not been watching Cat Vid at all prior to Smith's entry. See Bronston v. US for the "literal truth" requirement.
Second, the statement has to be material, not just false. We've covered this – there is nothing in evidence indicating that the statement is material. Third, the prosecution must prove that defendant knew that the statement is false. Although you stipulate a material fact, this is not possible in the real world – the prosecution cannot stipulate that the defense knows that the statement is false. They must introduce evidence proving that he knew that the statement is literally false. It's not possible to subpoena the contents of a person's mind, and without any evidence regarding knowledge, there can be no conviction. So, knowing all of this, the prosecution cannot prosecute him for perjury, until you change the scenario.