Once upon a time, people could erect an altar wherever they liked and offer sacrifices to God upon it. Abraham did it in Genesis, Gideon did it in Judges, and Saul did it in I Samuel, among many others. But once the Temple was established, it became the sole location where sacrifices could be offered. Private altars, called bamos, were then outlawed (although before Chizkiyahu–King Hezekiah–the ban was not enforced by the authorities). However, even while people were still permitted to offer sacrifices on private altars, this did not include the korban Pesach. Even before the permanent Temple was built, the korban Pesach could only be offered in the Mishkan (Tabernacle).
The prohibition makes absolutely perfect sense given the importance of the Passover sacrifice. Failing to offer the korban Pesach was one of only two positive mitzvos that could result in a penalty of kareis (spiritual excision–see Mitzvah #5). It had many other aspects in which it was treated differently from all other sacrifices. It's perfectly logical given the korban Pesach's unique status that it would be held to a higher standard and be barred from bamos even at times when bamos were permitted.
In one sense, this mitzvah only applies in Temple times, since we do not currently offer the korban Pesach. In other ways, this mitzvah applies even today in that, if one were to offer a Paschal lamb in his backyard, he would be in violation.
This mitzvah is exceptional in that it is the only one in the Sefer HaChinuch that is not in the Rambam’s Sefer HaMitzvos. This is especially surprising given the number of times the Sefer HaChinuch says that he prefers the Ramban’s emendations “but whatchagonnado, I said I’m going to follow the Rambam’s list” (loosely paraphrased). One can only speculate as to the reason the Sefer HaChinuch deviates in this case but he appears to have based this mitzvah on an earlier draft of the Rambam’s Sefer HaMitzvos.
In any event, the Rambam removed this mitzvah from his revised list and replaced it with his negative mitzvah #149, a prohibition against non-kohanim eating certain sacrifices based on Exodus 29:33 (compare with Mitzvah #102, the obligation for kohanim to eat sin offerings and guilt offerings).
The basis to exclude this commandment from the list of 613 mitzvos is that it does not conform to the Rambam's third principle, that mitzvos must be meant for all generations, not just for a limited time. For example, the commandment not to gather more or less than a certain amount of manna only applied to the generation that left Egypt. Similarly, only the generations that were permitted to use bamos needed a command “except for the korban Pesach.” Since the Temple was built and bamos were completely forbidden, this commandment ceases to be applicable.
In the Talmud, this law is discussed in first chapter of Megillah (9b). It is found in the Mishneh Torah in Hilchos Korban Pesach 1:3 but only in the context of the generations that were permitted to sacrifice on bamos.