[Abridged] Deep optical observations of the spectra of 12 Galactic planetary nebulae (PNe) and 3 Magellanic Cloud PNe were presented in Paper I by Tsamis et al. (2003b), who carried out an abundance analysis using the collisionally excited forbidden lines. Here, the relative intensities of faint optical recombination lines (ORLs) from ions of carbon, nitrogen and oxygen are analysed in order to derive the abundances of these ions relative to hydrogen. We define an abundance discrepancy factor (ADF) as the ratio of the abundance derived for a heavy element ion from its recombination lines to that derived for the same ion from its ultraviolet, optical or infrared collisionally excited lines (CELs). All of the PNe in our sample are found to have ADFs that exceed unity. There is no dependence of the magnitude of the ADF upon the excitation energy of the UV, optical or IR CEL transition used, indicating that classical nebular temperature fluctuations--i.e. in a chemically homogeneous medium--are not the cause of the observed abundance discrepancies. Instead, we conclude that the main cause of the discrepancy is enhanced ORL emission from cold ionized gas located in hydrogen-deficient clumps inside the main body of the nebulae. We have developed a new electron temperature diagnostic, based upon the relative intensities of the OII 4f-3d 4089A and 3p-3s 4649A recombination transitions. For six out of eight PNe for which both transitions are detected, we derive O2+ ORL electron temperatures of <300 K, very much less than the O2+ forbidden-line and Balmer jump temperatures derived for the same nebulae. These results provide direct observational evidence for the presence of H-deficient, cold plasma regions within the nebulae, consistent with gas cooled largely by infrared fine structure and recombination transitions.