This discrepancy was noticed by the Radvaz (Shu"t Chelek 3 Simman 585), Mishneh LeMelech (Parshas Derachim, Derech Mitzvoseicha Chelek 4 Simman 467), and the Minchas Chinuch (Mitzvah 467), among others.
As mentioned, the Chinuch leaves out the mitzvah against a zar eating terumah, and he replaces it with the prohibition against bringing the korbon pesach on a bamas yachid. He brings this as Mitzvah #467.
The Mishneh LeMelech and Rav Yerucham Perlah (Sefer HaMitzvos LeRasag #174) explain that the Rambam left this Mitzvah out because he felt it was only stated for a specific time (following Shoresh 3), ie: when bamos were permitted. The question is, why did the Chinuch include it, especially since he was so loyal to the Rambam? This in addition to the fact that the Chinuch doesn't even acknowledge his deviation from the Rambam (and Ramban).
Rav Chaim Heller, in his introduction to his version of Sefer HaMitzvos, explains that soon after Sefer HaMitzvos was published and subsequently translated, mistakes began to appear. He cites the Teshuvah of Rabbeinu Avraham ben HaRambam (Maaseh Nissim Simman 2) to Rav Daniel HaBavli who asked why the Rambam counted the prohibition of bringing the korbon pesach on a bamah when the mitzvah wasn't for all time. Rabbeinu Avraham responds that there is no such mitzvah in the sefer of the Rambam and it's entirely a mistake. Rav Heller assumes that Rav Daniel HaBavli had a version of Sefer HaMitzvos with this mistake in it, and suggests that perhaps this mistake was also in the version the Sefer HaChinuch had. This would explain why the Sefer HaChinuch deviated from the Rambam that we have (although this is not a definitive explanation, it's the best I found).
(Credit to the Frankel edition of the Rambam for providing a lot of the sources.)
I subsequently found the Artscroll version of Sefer HaChinuch points to a different approach to this discrepancy, found in Mayan HaChochmah by Rav Noach Chaim Tzvi Berlin, which is as follows:
The Chinuch noticed the Rambam left out all the halachos of bamos, yet put the halacha prohibiting the korbon Pesach on a bama. This must mean that bamos are no longer relevant today as it is forbidden to bring a korbon outside the Temple. Since the Rambam put the halacha specifically in the halachos of korbon Pesach, that halacha must be relevant even today.
The Chinuch must also hold like Tosafos in Zevachim 59a, who says everyone agrees that someone who slaughters a korbon today outside the Temple is exempt from kares. Therefore, the prohibition of korbon Pesach would be a novelty, punished by kares, and is fitting to count in the 613 mitzvos. However, the Rambam disagrees with Tosafos and holds slaughtering a korbon today outside the Temple does get punished with kares. That means there's nothing unique about korbon Pesach, just another אזהרה, which isn't worth counting in the 613.
All this explains why the Chinuch added this mitzvah, but not why he discounted a zar eating terumah. The Mayan HaChochmah (I can't find where) says that the Chinuch held that that verse (Exodus 29:33) is referring to the miluim, the inaugural korbonos ceremony. Therefore, that prohibition was only for that time, and isn't to be counted in 613 (Artscroll says Maharam Schik #103 also says this).
However, Artscroll points out this is hard to understand, as the first half of that verse is counted by the Chinuch as a mitzvah, meaning not exclusively about the miluim. Why wouldn't this verse be treated the same. They point to Maharam Schik #103 for a possible resolution, although I don't get how he resolves it (says it's just a ייתור דקרא so not worth counting).
Of course, the first explanation seems a lot simpler and is thus more likely to be correct.