제가 보기에는 payroll office에서 잘못한 것 같습니다.

F/J 비자라고 해서 무조건 Nonresident Alien이 되는 것은 아니고
그 이전의 체류기간이 길다면 Resident가 됩니다.

원글님은 이전에 이미 미국에 오래 거주했기 때문에 Resident라고 봐야 하고
social security/medicare tax도 냈어야 한다고 생각합니다.

외국 사람이 연방 세법상 Resident인지 Nonresident인지 결정하는 것은
실제 미국에 체류한 날짜를 세어서 계산하는 ‘Substantial Presence Test’를 따릅니다.
F/J 체류신분에서 Nonresident가 되는 것은 ‘Exempt Individual’으로서
실제 체류했던 기간을 이 날짜 계산에서 제외시키기 때문입니다.

이를 위해서 Form 8843을 작성해야 합니다.
그런데, 원글님의 경우에는 Form 8843에서 다음 항목이 ‘Yes’가 되고
예외 조항에도 해당되지 않기 때문에 ‘Exempt Individual’을 적용할 수 없습니다.
그러므로, Resident가 됩니다.

* http://www.irs.gov/pub/irs-pdf/f8843.pdf

8. Were you present in the United States as a teacher, trainee, or student for any part of 2 of the 6 prior calendar years (2007 through 2012)? …………………… Yes No

If you checked the “Yes” box on line 8, you cannot exclude days of presence as a teacher or trainee unless you meet the Exception explained in the instructions.

즉, Form 1040으로 Resident 부부 조인트로 세금 보고를 하고
2013년에 내지 않은 소셜/메디케어 택스를 내는 것이 법 규정에 맞을 것입니다.

Form 1040에 보면, 이렇게 내지 않은 소셜/메디케어 택스를 내는 항목이 있습니다.
57. Unreported social security and Medicare tax from Form: a 4137 b 8919

그런데, Payroll office에서 그간 내지 않은 소셜/메디케어 택스의 Employer 부담분인
50%를 지금 내줄지 모르겠군요.

Resident로 세금 보고를 하면서
소셜/메디케어 택스를 내지 않아도 그냥 모르고 지나가는 경우도 있고
나중에 밀린 세금을 내라는 편지가 오는 경우도 있다고 들었습니다.

2010년에 J-1으로 바꾸셨다면, 2011,2012년 세금 보고는 어떻게 하셨는지 모르겠군요…
그 사이에 체류신분에 아무러 변화가 없는데, 그때는 Resident로 하고
2013년에는 Nonresident로 하는 것은 이상하지 않나요?

참조: http://sorine.kseane.org/sorine_tax_faq.html#ResidentNonresident
(9) Resident/Nonresident: 세금보고에서 Resident란 영주권자인가 ?