The linewidth of the resonances in the single-electron tunneling spectra has been investigated for PbSe semiconductor nanocrystals (NCs) with scanning tunneling spectroscopy at low temperature. The linewidth of the resonances corresponding to tunneling through the first conduction and valence levels is found to increase with decreasing size of the NCs. Based on theoretical calculations, this broadening is mainly induced by the coupling between the tunneling electrons and the longitudinal optical phonon mode of the NC, and by the splitting of the degenerate electronic levels between the different L-valleys in the Brillouin zone. For the smallest sizes, it is shown that the intervalley splitting is the major source of broadening.