Rashi writes in P' Beshalach that there were three mitzvos given at Marah, the first camp reached after crossing Yam Suf: the mitzvos of Shabbos, parah adumah, and dinim (establishing a justice system). There are a number of difficulties with this Rashi. While it is true that there were mitzvos given at Marah, there are different views in Tanaim as to what they were -- Rashi's list of three does not match any of those views. Furthermore, Rashi himself comments in Parshas VaEschanan that the words "ka'aseh tzivcha" in the mitzvah of kibud av v'eim alludes to the fact that this mitzvah was given at Marah, yet kibid av is not mentioned in Rashi's list here. I want to focus on a third difficulty, which is not necessarily a problem with Rashi, but rather is a problem with the chronology of the Midrash. Chazal tell us (Shabbos 118) that if only Klal Yisrael had observed one Shabbos in the midbar they would have achieved complete geulah; however, that very first Shabbos was desecrated by the people who went out to collect mon. Tosfos (Shabbos 87b) already points out that if the laws of Shabbos were already given at Marah, then the very first Shabbos in the midbar was not desecrated. The very first Shabbos occurred immediately after Marah, which was before the mon started to fall. Why don't Chazal count this first Shabbos?
Tosfos doesn't really resolve the issue, but the Maharal in Gur Arye does. He suggests that the laws of Shabbos given in Marah consisted only of the mitzvos aseh of Shabbos, but no prohibitions. It was only once the "shall nots" of Shabbos were introduced, e.g. not collecting the mon on Shabbos, that Shabbos really counted as observed.
What does the Maharal mean? (And I'm sorry to say that even if you look at R' Hartman's beautiful notes, they won't help you here.) Why should shmiras Shabbos not count just because there were not yet any prohibitions attached to it?
I would like to suggest that this fits perfectly with a chiddush we discussed two weeks ago (here). The gemara (Shabbos 69) discusses a case of someone who violates all 39 melachos but still has some sense that it is Shabbos. Asks the gemara, if the person does every melacha in the book, what does he/she know about Shabbos? Answers the gemara, he/she knows there is an issur of techumin. Why, asks Tosfos, did the gemara not answer that the person knows there are mitzvos aseh associated with Shabbos? Why make the assumption that techumin is an issur d'oraysa (a major debate starting with the Tanaim) when the gemara could play it safe and say the person was aware of the mitzva aseh of kiddush on Shabbos?
Rav Hershel Shachter answers that the concept of kedusha by definition entails issurim, prohibitions. A kohen has a certain level of kedusha because he cannot marry certain women. Eretz Yisrael has kedusah because there is an issur of tevel associated with produce grown there. An awareness of "Shabbos kodesh" means specifically a sense that there are things that cannot be done on Shabbos.
Since there were no prohibitions associated with the mitzvah of Shabbos given at Marah, that first Shabbos was lacking a full kedushas Shabbos and therefore did not count. It was only once the issur of collecting mon was introduced that a full kedushas Shabbos truly existed.