R' Elchonon Wasserman (Or Elchanan pg. 258) posed this question to the Imrei HaEmes (Gerrer Rebbe), who explained that Korach didn't deny Moshe's authenticity, but rebelled against it. There is a difference between someone who doesn't believe versus someone who doesn't accept.
This question is also asked by R' Chaim Kanievsky in Taama Dekra. He answers that they weren't denying Moshe's authenticity, but accused him of davening for superiority - to which he replied כי לא מלבי. (See Netziv in Haamek Davar, who explains כי לא מלבי similarly).
However, this answer contradicts the Rambam (Yesoidei Hatorah Ch 8), who explicitly writes that they denied Moshe's nevuah.
Another answer (posed by the Steipler Gaon and R' Shach) is that וגם בך יאמינו לעולם was a promise that no one would ever naturally deny Moshe Rabbeinu's authenticity. However, through exposure to kefirah or timtum of maachalos asuros and other spiritually damaging entities, it is possible to lose the natural purity.
[These answers are taken primarily from R' Chaim Kaufman's Mishchas Shemen, see inside for further discussion.