The gemara says that 3000 halachos were forgotten when Moshe died. The people asked Yehoshua to retrieve the lost halachos from Hashem to which he responded לא בשמים הי. Generations later they asked Shmuel to retrieve it, to which he responded אלה המצות - שאין נביא רשאי לחדש דבר מעתה. Both responses seem to be similar, the only Navi who is able to transmit Torah from Hashem is Moshe. Once it was transmitted by Moshe, it was not simply shared with the Jewish people, but literally given to the Jewish people so that all decisions had to take place following a halachic system. The only way to retrieve lost halachos is to do as Asniel Ben Kenaz did, to use principles available and analysis (piplul) to retrieve the lost information. Even when machlokes develops, the only way to decide who is correct is using the system of אחרי רבים להטות as the gemara says was done after Moshe died - אם רבו מטמאין טמאו, אם רבו טהורין טיהרו (although rashi explains that the machlokes about semicha was the first machlokes ever to exist, that means it was the first machlokes where they couldn't reach an agreement by voting, but surely there was machlokes much earlier - the gemara in Sanhedrin (2nd perek) suggests that Shaul and Dovid had a halachic debate about המקדש במלוה).
It is unclear from the gemara why when Yehoshua was asked to retrieve the halachos his response was לא בשמים היא, whereas Shmuel responds אלה המצות - שאין נביא רשאי לחדש דבר מעתה, since they are essentially the same point. The Maharsha asks this question as suggests that for Yehoshua it may not have been a violation of אלה המצות since he had heard these halachos from Moshe himself, just that he forgot them. He needed to be reminded of them, but didn't need to learn them from scratch. Therefore, it wouldn't be a violation of introducing something new, nevertheless couldn't be done due to the limitation of לא בשמים היא.
The gemara in Megilla 3a says that the "tzofim", meaning the nevi'im, introduced the מנצפ"ך, meaning all the letters that have a different font when they appear at the end of a word. The gemara asks how could the nevi'im have introduced something so fundamental, it is a violation of אלה המצות - שאין נביא רשאי לחדש דבר מעתה. The gemara answers - שכחום וחזרו ויסדום. Originally, they were given by Moshe, but they were lost and the nevi'im were used to retrieve the lost halachos. This clearly implies that even when Nevi'im restore lost halachos that they have never heard before, it isn't a violation to אלה המצות. Why does our gemara consider the restoring of forgotten halachos to be a violation of אלה המצות?
It seems that the answer lies within the words of Rabbeinu Chananel in Megillah who writes:
ואקשינן ואלה המצות שאין נביא רשאי לחדש דבר מעתה, ופרקינן לעולם מתוקנים היו, וכן היה מסורת בידם מהנביאים להיות הפתוחים באמצע תיבה והסתומים בסוף תיבה, ושכחום וחזרו הצופים ויסדום
Rabbeinu Channanel seems to explain that they had a mesorah from the nevi'im about these letters and exactly where they should be placed, the function of the nevi'im who restored them was only to remind people of the mesorah. It seems from here that once it has entered the chain of mesorah, it can be restored by nevi'im, but when taught by Moshe and immediately forgotten, since it never entered the realm of מסרן ליהושע ויהושע לזקנים וזקנים מסרוה וכו, it can't be restored by nevi'im.