Is the interest on the loan from my 401(k) deductible? We used it for a down payment on our primary residence.

No. Interest on a 401k loan is not deductible, no matter what the money was used for.

There are actually situations where the interest on a 401(k) loan would be deductible, but they are very rare.

For example, let's say you were borrowing from your 401(k) to finance the purchase of a rental property -- this interest would be considered deductible if (and only if) the funds you are borrowing from your account are NOT your own elective deferrals. Essentially, you'd have to borrow exclusively from your employer's matching / profit sharing funds and have to prove that they were used for a deductible reason (i.e. a rental property).

How do I prove that I borrowed from ONLY my employer matching, which was actually enough to cover my modest loan?