The spurious interaction of an electron with itself - self-interaction error - is one of the biggest problems in modern density-functional theory. Some of its most glaring effects, such as qualitatively incorrect charge separation upon dissociation, can be removed by an approximate self-interaction correction due to Perdew and Zunger (PZ) (Perdew, J.; Zunger, A. Phys. Rev. B 1981, 23, 5048). However, the correction introduces an explicit dependence on the occupied orbital densities, which makes proper minimization of the functional difficult. Previous work (Vydrov et al., J. Chem. Phys. 2006, 124, 094108) has suggested that the application of the PZ correction results in worse atomization energies than those obtained with the uncorrected parent functional. But, it has only recently been found that the correct minimization of the PZ energy functional requires complex-valued orbitals, which have not been used in previous work on atomization energies. Here, we study the effect of the proper use of complex-valued orbitals on the atomization energies of molecules in the W4-11 data set (Karton, A.; Daon, S.; Martin, J. M. Chem. Phys. Lett. 2001, 510, 165). We find that the correction has a tendency to weaken the binding of molecules. The correction using complex-valued orbitals is invariably found to yield better atomization energies than the correction with real-valued orbitals. The correction applied to the PBEsol exchange-correlation functional results in a functional that is more accurate than the (uncorrected) PBE functional.