If you're concerned about the ethics of how you or your wife answers such a question (as your handle leads me to suspect and appreciate), then I would offer this:
There's a difference between, on the one hand, stating positively that it is something other than tobacco, if that positive statement can be true (e.g. Cosmic's suggestion of "tea," since it is not impossible that the recipient could choose to steep the tobacco in hot water), and on the other hand stating negatively that it is not tobacco (if asked directly, as your wife was).
And I'm sure that "tea" is not the only justifiable positive label that could be used. Just off the cuff, "herbs and spices" comes to mind, as does "incense." All true answers.
In light of this distinction between various true positives and the one false negative, I would seek any venue for shipment which permits you to make positive statements and avoid questions.
(Perhaps a different post office, or registering a package online for them to pick up, etc.)
