You know you are thinking correctly when many Acharonim, including the PNEI YEHOSHUA, CHASAM SOFER, and SFAS EMES ask your question. There are many explanations given. The Sfas Emes explains that although Rebbi Yehudah differentiated between old and new due to the old candle being Mi'oos, Ula thought that Rebbi Yehudah continued by saying that a Kos, K'arah, and Ashashis are even Muktzah if they are new, because they are considered Mi'oos even before they have been used. The Pnei Yehoshua takes a similar approach, adding that Ula did not know of the Beraisa brought later in the Gemara, which clearly shows that Rebbi Yehudah holds of Muktzah Machmas Isur as well as Muktzah Machmas Mi'oos. The Chasam Sofer (Hashalem, see at length) understands that Ula had a different text of the Beraisa quoted in our Gemara, which is found in the Yerushalmi.

In my opinion, it is understandable why we would not attribute the Beraisa to Rebbi Meir. Rebbi Meir, as RASHI points out (DH "Chutz"), holds only of Machmas Isur but not Mi'oos. He stated that one can move all Neiros besides those lit on Shabbos. Why would he then say "However, a Kos, Ke'arah, and Ashashis one should not move from their place." If he is talking about ones that were lit that Shabbos, why should they be different than a Ner? If they were not lit, why should they be Muktzah? It therefore does not seem that Rebbi Meir is the author of this statement.

Kol Tuv,

Yaakov Montrose