You can't ever remove an item from the All Commands list so it should still be there somewhere. Dragging items out of it to the toolbar copies them rather than moving them.
Watch the Toolbar Editing video tutorial to see exactly what you need to do.
If it isn't working then the problem may be solved by this FAQ: Unable to drag new buttons from Customize to Toolbars