Shulchan Aruch HaRav (O.C. 310:16) lays out the general history of the prohibition of Mukza (Based on Shabbos 123b):
בימי נחמיה בן חכליה שהיו העם מזלזלים באיסורי שבת כמ"ש בימים ההם ראיתי ביהודה דורכי[ם] גתות בשבת ומביאים הערימות וגו' עשו חכמים סיג וגדר לאיסור הוצאה וגזרו על כל הכלים אע"פ שמלאכתם להיתר שלא לטלטלם כלל אפילו לצורך תשמישן המיוחד להם חוץ מן כוסות וקערות וסכין וכיוצא בהם מהכלים הצריכים ביותר לסעודת השבת.
ואח"כ כשראו חכמים שחזרו העם להזהר קצת באיסורי שבת חזרו והתירו לטלטל כל כלי שמלאכתו להיתר לצורך גופו או לצורך מקומו.
ואח"כ כשראו שחזרו העם להזהר יותר חזרו והתירו לטלטל כל כלי שמלאכתו להיתר אפילו לצורך הכלי עצמו אבל לטלטל שלא לצורך כלל עדיין לא נמנו עליו חכמים להתירו ונשאר עומד באיסורו שנאסר בגזרת חכמים שבימי נחמיה בן חכליה
To summarize:
In the days of Nechemia, due to a general severe laxity in keeping Shabbos, all vessels were prohibited except a limited number of types necessary to eat the meal. This was done as a סיג וגדר לאיסור הוצאה - a fence around the prohibition of carrying. This prohibition was subsequently relaxed, ultimately to Muktza as it is today.
Although I haven't found anything definitive on exactly when the prohibition was relaxed, it does seem that this was not in the times of Nechemia's Beis Din (but if something definitive could be found otherwise, that would answer the question).
However, The Rambam writes (Mamrim 2:3):
דברים שראו בית דין לגזור ולאסרן לעשות סייג אם פשט איסורן בכל [ישראל] אין בית דין גדול אחר יכול לעקרן ולהתירן אפילו היה גדול מן הראשונים
Things which a Beis Din saw fit to degree and forbid to do as a fence - if the prohibition spread to all of Israel another Great Beis Din (i.e. a Sanhedrin) cannot remove it and permit it, even if they were greater than the first ones.
If so, how could the prohibition have been subsequently relaxed?