The Mishna Berura in 494:12 says that he heard that another explanation: when Klal Yisroel heard the Aseres Hadibros, they were given all 613 mitzvos, and so they became aware that neveila is assur. Their kitchens were all treif. When they came home, they had nothing kosher to eat other than milchiks, because making fleishik takes a long time, from the shechita through the cooking, and so they ate milchiks, and we make a zaicher for this.
Ovi Mori (shlita, may Hashem give him a speedy and complete recovery bi'soch sh'or cholei Yisroel) Zatzal, a talmid of Slabodkeh in Lithuania, asked a very interesting question. The Gemora in Shabbos 86b says that everyone agrees that the aseres hadibros were given on Shabbos. So what are they talking about when they say that shechita and all the melochos required long preparation— they couldn’t do any of that on that day at all! They couldn't even start to do anything involving fleishiks until after Yomtov, which was Shabbos that year, was over!
I said a teretz on this kashe in Summer, 2000: since bein hashmoshos, Friday night, it was still before matan Torah, and the tzivui of Shabbos only took place in the morning, the dinim of Shabbos could not be operative (chall) that day. For Shabbos Breishis to be chall, it has to be chall in the beginning of the day, at Tzais, not in the morning. That is why the Chazal were kovei’a that the dinim of Shabbos (such as shvisa for techumim and hachana regarding muktzah) are determined according to their status Bein Hashmoshos. (See important update at end of post.)
Harav Dr. Avremi Isenberg immediately asked, but Shabbos was given in Marah, or at the latest with the mahn, long before Mattan Torah, so they knew of and kept Shabbos long before the Aseres Hadibros were given! I answered with the shittas haRambam in Pirush Hamishnayos in the end of the seventh perek of Chullin, that all the mitzvos we do today are only because of the commandment on Sinai, and not, e.g., in the case of eiver min hachai, because of the earlier tzivui to the bnei Noach, or, in the cases of Millah and Gid Hanasheh, because of the commandment to Avraham and Yaakov. (The Mishneh Limelech in Melochim 10:7, almost at the end, brings this Rambam, and mentions the Yefei Toar that explains that the Rambam just means that we should do them because of the tzivui of Sinai which is more choshuv, but not that the earlier tzivui is boteil, but he argues with the Yefai Toar, and holds that they are completely boteil.) And the Gur Aryeh in Beshalach (Shemos 15:25) says clearly that the mitzvos of Marah cannot be Torah, because it is not possible that Torah Shebal Peh should precede Torah Shebichsav, and that the mitzvos of Marah are exactly the same as "mila to Avrohom, and Gid Hanoshe to Yaakov, and the seven mitzvos of the bnei Noach". So, if the earlier tzivui was boteil at the time of Matan Torah, the mitzvos of Marah are also boteil. At the moment of Mattan Torah, the Shabbos of Marah was supplanted by the new mitzvah of Shabbos. This new Shabbos could not begin in middle of the day. So the dinim of Shabbos were not chal until the next week.
Furthermore, there is a great deal of discussion as to whether the mitzvah of Shabbos which they received at Marah was complete or binding even when they received it.
1. See Oneg Yomtov Introduction #22, who says that they only received the Mitzvoh of Zochor es yom hashabbos, not the din of Shomor, which means that none of the prohibitions were given until Mattan Torah.
2. The Netziv in his Teshuvos says that it would have been impossible for Hashem to just drop a bomb on the nation and command them to keep Shabbos without time to learn what keeping Shabbos entails. So the tzivui of Marah was only to learn the dinim.
3. There is a machlokes Rovo and Rav Acha bar Yakov in Maseches Shabbos 87 as to whether they were given the din of Techumim in Marah. Tosfos there says that according to Rovo they were also not given the law of carrying from one reshus to another. The Ritva adds that they were not given the law of mechameir achar b’hemto.
4. The only reason Hashem was angered when people went out to gather the Mahn on Shabbos in Marah was because it was a mitzvah connected to the rules of the Mahn, not necessarily because of the din of Shabbos.
5. Rashi avoids dealing with this issue by saying that the Shabbos commandment of Marah was "parshiyos le’his’aseik bohem," not necessarily that they were mandatory, rather that they were instructed to learn about Shabbos. As Harav Dovid Zupnik, a talmid of Mir in Europe, (a tzadik and a great talmid chacham, whose Levayah is, unfortunately, today, May 22, 2007- Erev Shavu'os '67-- Boruch Dayon Ho'emes), said, from Rashi in Shemos 16:22 it is clear that Moshe had only given them the most general idea of what Shabbos entailed. First of all, Rashi says they were given "parshiyos le'his'aseik bohem," not "Mitzvos le'his'aseik bohem," as Rashi had said in the context of Korbon Pesach in Mitzrayim. Second, if he had taught them more about the dinim, Dosson and Avirom could not have gone out to gather Mohn on Shabbos, because the grandparents of the people on Bar Ilan would have been there yelling "Shabbes! Shabbes!"
Thus, we are justified in saying that the Shabbos of Marah was qualitatively different from the Shabbos of Mattan Torah. And even if there was a complete tzivui of Shabbes in Marah, as indicated according to Rav Acha bar Yaakov, it was supplanted by the tzivui of Mattan Torah.
Update, Pesach 'ayin beis:
1. It turns out that this question, whether Shabbos can begin after Shkiah/Tzeis have passed already, or it has to begin in the beginning or not at all, is a machlokes the Rosh and his rebbi, the Maharam mei'Ruttenberg. See Rosh Moed Kattan perek 3 number 96, especially with the Bach's girsa there. Amazing. I also saw that Reb Elchonon talks about it at length in Beitza 17, and it's really worth seeing it inside.
2. Another testament to the spread of Torah in our generation: Rabbi Etan Schnall directed me to a sefer entirely devoted to the topic of Shabbos between Mara and Mattan Torah, called Mitzvas Hashabbos by Rabbi Elchonon Adler, 2008. To save you time, the table of contents is located on page 13 of the Hebrewbooks pagination.
3, Etan directed me to this paragraph, from the new Dirshu edition of the Mishna Berura: