Thanks for the replies!
I read through Pubs 54, 514, and the instructions for Form 1116 and could not find ANYTHING related to that type of contribution. It does not even appear in Form 1116's "Foreign Taxes Not Eligible for a Credit."
In fact, the following passage from Pub 514 led me to think that we COULD deduct our NI contributions: "A foreign tax imposed on an individual to pay for retirement, old-age, death, survivor, unemployment, illness, or disability benefits, or for similar purposes, is not payment for a specific economic benefit if the amount of the tax does not depend on the age, life expectancy, or similar characteristics of that individual."
Therefore, since the payment is not for a specific economic benefit, it is okay to take a credit for the tax.
However, the very next paragraph says: "No deduction or credit is allowed, however, for social security taxes paid or accrued to a foreign country with which the United States has a social security agreement."
Are the NI contributions considered "social security taxes?" I guess I was thinking of them more as health insurance, etc. benefits.
I'm certainly not questioning the sage advice I've received; I'm just wondering how on earth someone would deduce the answer to this question without the good people on this forum!