I would recommend to check the "tax category" field of the product edition page of that product and make sure that it correspond to the tax category that you selected in your tax rule (that you can see via the menu System>Taxes).
I have used Default tax category in the tax rules and in products I use Default tax category! The funny thing is that it works for most products but not all! Any other ideas to fix the problem.
The problem comes from the fact that you had set a tax category to your variants in some way before.
As you had provided a backend access before, I've created a mass action (menu system>Mass actions) to force the tax category of all your variants to the default tax category and it works fine now.
