Rebbi Shimon ben Gamliel stated that the two most festive days for Yisrael are 15 Av and Yom Kippur. (Taanis 26b) The Gemara understands that the joyous nature of Yom Kippur arises from the forgiveness that was granted on that day, but it questions why 15 Av is so special. (Ibid. 30b) Many answers are given, but one of them is a little intriguing.
Rabbah bar bar Chanah stated that 15 Av was the day that the generation of Klal Yisrael that had exited Mitzrayim had ceased to die. (Ibid.) Rashi cites from a Midrash that every 8 Av the crier would go out and call to the nation telling them to go out and dig. The nation would dig graves and sleep in them that evening. The next morning, 9 Av, the crier would call out and tell all those still alive to come out of their graves. During the last year in the Wilderness this occurred, but the decree had been lifted so none were left dead in their graves. The people thought that perhaps they had erred in their calculations for the month and continued this practice until 15 Av when they noticed that the Moon was full and by now certainly 9 Av had passed. It was then they knew that the decree had been nullified. (Rashi Taanis 30b, also see Rashbam Bava Basra 121a)
What is interesting is that the rule of calendar regulation is that even if the High Court proclaims the wrong day to be Rosh Chodesh, it is binding. (See Rosh Hashana 25a) So, why did the people think they had made any mistake whatsoever? On 9 Av they should have realized that the decree was over as soon as they all walked out of their graves. Even if the wrong date had been chosen, since it would have been done formally it would have been 9 Av! It is unlikely that the official crier called to the people without first asking what date it was. Even if one were to assume that he did, it seems unreasonable that the people did not know that it was 8 Av! It seems that they knew what date it was on the calendar, but thought that it was not binding because the Moon did not display the growth normally seen by an 8 day Moon! This Midrash seems very difficult to understand when viewed together with the halachic assessment that Beis Din's ruling is final for Rosh Chodesh even if the Moon was not really seen on that day!
Perhaps the answer is something along the lines of the following. While it is true that Klal Yisrael has been empowered to proclaim the date of Rosh Chodesh, who says that the original decree of Hashem was to be carried out on 9 Av and not the ninth day of the new Moon at the time of Av. Meaning, Klal Yisrael has to place its holidays in season specific times and they have been charged with regulating the calendar. Pesach must be in the spring, Shavuos at the harvest, and Sukkos at the time of gathering. We are given the ability to sanctify these days via our calendar and its regulation. Thus, we state that Hashem is Mekadesh Yisrael VeHazmanim (sanctifies Yisrael and the times). Included in this phrase is that we are to sanctify the holidays to be in their proper seasons, times. Tisha B'Av has no requirement to be in a specific season. Perhaps, Hashem's decree was based on the second 9 day old Moon after the summer solstice and this would normally be on 9 Av. Klal Yisrael was using its calendar, which was generally synchronized with the lunar cycle. However, it was possible for the calendar and the lunar cycles to be off (as is very often the case not only throughout history but even in today's day and age). Thus, they went out on 8 Av assuming it was also the eighth day from the new Moon. It wasn't until they saw the full Moon that they knew that they had not erred.
Nowadays, we commemorate 9 Av due to rabbinic injunction, therefore, it has now become a day in the calendrical year like all other holidays whether they are rabbinic or biblical. It is of note, though, that if the above is true then the decree had nothing to do with 9 Av technically. It had to do with the 9th day since the new Moon. This most often would have fallen on 9 Av and probably did the year the spies came back with their awful report.