The gap oscillations caused by a magnetic flux penetrating a carbon nanotube represent one of the most spectacular observations of the Aharonov-Bohm effect at the nanoscale. Our understanding of this effect is, however, based on the assumption that the electrons are strictly confined on the tube surface, on trajectories that are not modified by curvature effects. Using an ab initio approach based on density functional theory, we show that this assumption fails at the nanoscale inducing important corrections to the physics of the Aharonov-Bohm effect. Curvature effects and electronic density that is spilled out of the nanotube surface are shown to break the periodicity of the gap oscillations. We predict the key phenomenological features of this anomalous Aharonov-Bohm effect in semiconductive and metallic tubes and the existence of a large metallic phase in the low flux regime of multiwalled nanotubes, also suggesting possible experiments to validate our results.