Tunneling spectroscopy was performed on Nb pieces prepared by the same processes used to etch and clean superconducting radio frequency (SRF) cavities. Air exposed, electropolished Nb exhibited a surface superconducting gap delta=1.55 meV, characteristic of clean, bulk Nb. However the tunneling density of states (DOS) was broadened significantly. The Nb pieces treated with the same mild baking used to improve the Q-slope in SRF cavities, reveal a sharper DOS. Good fits to the DOS were obtained using Shiba theory, suggesting that magnetic scattering of quasiparticles is the origin of the gapless surface superconductivity and a heretofore unrecognized contributor to the Q-slope problem of Nb SRF cavities.