Density functional theory calculations are often used to interpret experimental shifts in core level binding energies. Calculations based on gradient-corrected (GC) exchange-correlation functionals are known to reproduce measured core level shifts (CLS) of isolated molecules and metal surfaces with reasonable accuracy. In the present study, we discuss a series of examples where the shifts calculated within a GC-functional significantly deviate from the experimental values, namely the CLS of C 1s in ethyl trifluoroacetate, Pd 3d in PdO and the O 1s shift for CO adsorbed on PdO(101). The deviations are traced to effects of the electronic self-interaction error with GC-functionals and substantially better agreements between calculated and measured CLS are obtained when a fraction of exact exchange is used in the exchange-correlation functional.