As someone with experience of these situations I'd say you should ask the payroll dept to contact the tax office and ask if it would be possible to have a tax credit cert issued on a week 1 / month 1 basis up to the end of the year.
Revenue should be accomodating, seeing as the problem arose as a result of an incorrect P2C issuing to your new employer from Revenue. You should suggest to the payroll dept. that they do it this way, and let them speak to Revenue: as strictly speaking they shouldn't be doing what they said they will about the 2k of tax.
That way your employer can correctly operate the PAYE system, and still pay you your "normal" salary, and you can then agree to have your tax credits for the next couple of years reduced to cover the underpayment that's arisen.