Hmm, that’s odd. I don’t remember needing anything like that when I opened a bank account. I think I only had to show my NIF, my passport, proof of address in Portugal, and proof of income. (I don’t even think they asked for my U.S. Social Security Number, but I’m not sure.)
Are you sure he wasn’t asking for the NIF? He said it specifically had to be a different U.S. tax number, but not your SSN? I would try going again and talking to a different person… maybe they will tell you something different or will know more about how to figure out what it is that you’re missing.