The decree on items that have a use on Shabbos: In the times of Nehemiah Ben Chakilia, when the people belittled the Shabbos prohibitions, as it says “In those days I saw in Judah [people] working in the threshing floor on Shabbos and carrying the stalks”. Thus the Sages made precautions and boundaries on the prohibition of carrying [items], and they made a decree on all vessels, even if they are designated for a permissible purpose, that they may not be carried at all, even for the use that they are designated for. This was with exception to cups and knives and plates and the like of vessels which are very much needed for the Shabbos meal.
The retraction of the decrees:  Now, after some time when the Sages saw that the population returned to being a little more careful about the Shabbos prohibitions, they then retracted and permitted to move any vessel which is designated for a permitted purpose [if he is moving it] in order to use it or its space. Later on, when they saw that the people returned to being even more careful, they then retracted [further] and permitted to move any vessel which is designated for permitted use, even [to move it] for the benefit of the vessel itself.
However to move it for no need at all the Sages still never voted to permit, and thus it remains under its original prohibition which was forbade by decree of the Sages of the times of Nechemiah Ben Chakilia.
Items without use-The original decree of Muktzah that existed prior to the Sages of the times of Nechemiah: [The above statement that the status quo until the times of Nechemiah was that there were no restrictions to move items, only referred to items that have a use on Shabbos], however an item which was not fit to be used on Shabbos, was forbidden to move even in the days of King David and King Solomon or [possibly] even beforehand.
Summary-When was the Muktzah prohibition instituted?
Items without use: The Muktzah decree against items that one sets his mind aside from was already instituted by the times of King Shlomo, if not before.
Items with use: However the decrees of Muktzah against objects which one has not set his mind aside from using, (Milachto Liheter) were instituted only later in the times of Nechemia ben Chakilia due to fear that one may come to carry to a public domain the items he is holding. Although this decree was revoked, parts of it still remained until today. This is the reason mentioned by the Ravaad, and is the second reason mentioned above.
The opinion of the Aruch Hashulchan:
The Aruch Hashulchan explains that the prohibition dates back to the times of Moshe, falling under the commandment of resting, which includes many matters the Sages decreed upon us, but were not explicitly mentioned as one of the 39 Melachos (see Rambam Shabbos 21/1). Thus these prohibitions carry close to the weight of a Biblical precept. In accordance with this, the reasons mentioned in Rambam (Shabbos 24/12) behind the prohibition are coming to explain their Biblical root, and being that the extra decrees by time of Nechemia were revoked, the Rambam doesn’t mention this reason behind the decree. This is the opinion mentioned in Aruch Hashulchan, however from the Alter Rebbe as we explained earlier the decrees weren’t totally revoked and the reason why there are limitations in moving a permissible object is due to the decrees made in the times of Nechemia. According to the Aruch Hashulchan these decrees were always in place.
 Lit. were disrespectful
 This is based on the story brought down in the Gemara in Shabbos (30:) that when David Hamelech passed away, Shlomo asked the sages how he could remove the body, thus showing that the laws of Muktzah were already instituted.
 Machmas Gufo and Chisoren Kis as will be shortly explained.
 Beginning of 308