Carbon nanotubes continue to be model systems for studies of confinement and interactions. This is particularly true in the case of so-called "ultraclean" carbon nanotube devices offering the study of quantum dots with extremely low disorder. The quality of such systems, however, has increasingly revealed glaring discrepancies between experiment and theory. Here, we address the outstanding anomaly of exceptionally large orbital magnetic moments in carbon nanotube quantum dots. We perform low temperature magnetotransport measurements of the orbital magnetic moment and find it is up to 7 times larger than expected from the conventional semiclassical model. Moreover, the magnitude of the magnetic moment monotonically drops with the addition of each electron to the quantum dot directly contradicting the widely accepted shell filling picture of single-particle levels. We carry out quasiparticle calculations, both from first principles and within the effective-mass approximation, and find the giant magnetic moments can only be captured by considering a self-energy correction to the electronic band structure due to electron-electron interactions.