In the local universe, there is good evidence that, at a given stellar mass M, the gas-phase metallicity Z is anti-correlated with the star formation rate (SFR) of the galaxies. It has also been claimed that the resulting Z(M,SFR) relation is invariant with redshift - the so-called Fundamental Metallicity Relation (FMR). Given a number of difficulties in determining metallicities, especially at higher redshifts, the form of the Z(M,SFR) relation and whether it is really independent of redshift is still very controversial. To explore this issue at z>2, we used VLT-SINFONI and Subaru-MOIRCS near-infrared spectroscopy of 20 zCOSMOS-deep galaxies at 2.1<z<2.5 to measure the strengths of up to five emission lines: [OII], Hbeta, [OIII], Halpha, and [NII]. This near-infrared spectroscopy enables us to derive O/H metallicities, and also SFRs from extinction corrected Halpha measurements. We find that the mass-metallicity relation (MZR) of these star-forming galaxies at z~2.3 is lower than the local SDSS MZR by a factor of three to five, a larger change than found by Erb et al. (2006) using [NII]/Halpha-based metallicities from stacked spectra. We discuss how the different selections of the samples and metallicity calibrations used may be responsible for this discrepancy. The galaxies show direct evidence that the SFR is still a second parameter in the mass-metallicity relation at these redshifts. However, determining whether the Z(M,SFR) relation is invariant with epoch depends on the choice of extrapolation used from local samples, because z>2 galaxies of a given mass have much higher SFRs than the local SDSS galaxies. We find that the zCOSMOS galaxies are consistent with a non-evolving FMR if we use the physically-motivated formulation of the Z(M,SFR) relation from Lilly et al. (2003), but not if we use the empirical formulation of Mannucci et al. (2010).