This is definitely your employer's foul-up.
Up until the start of 2008-9 it had been standard practice to issue a new notice to employers and employees with the new coding at the start of each new year, even when the codes changed by the 'standard' amount (i.e. 503L to 543L). When I chased for such a thing this year, was told it is in the small print on PAYE from HMRC that an employer can make the change on their PAYE system without formal notification - lo and behold it is in there. Ditto the recent change from 543L to 603L.
They will issue a code change if asked to do so (and they continue to initiate a new code for an employee for other reasons when the individual's code requires changing).