They're both right.

Payroll withholds according to the instructions you provide them in your W4 form. They did everything correctly according to what they were told. If they have incorrect instructions from you, then it would result in not withholding enough and owing in April. But they don't know your financial situation, hence the reason the W4 form exists.

File a new W4 form with your employer, and make sure the instructions are correctly followed.