What is going on can be explained completely in terms of exponent vectors. To do so we can map each generator $x^u -x^v$ of $J$ to the exponent vector $u-v \in \mathbb{Z}^n$. Conversely, for each integer vector $s\in \mathbb{Z}^n$ we can form a binomial $x^{s^+} - x^{s^-}$ where $s^\pm_i = \max(\pm s_i, 0)$ are the positive and negative part of $s$, such that $s = s^+ - s^-$. Now, take the integer vector images of a minimal generating set of $J$ and let $L_J$ be the sublattice of $\mathbb{Z}^n$ that they generate. This lattice is independent of the chosen generators and we have the following basic fact:
Prop. Let $S \subset L$ be any finite set of vectors spanning $L$ as a lattice. Then $J = \langle x^{s^+} - x^{s^-} : s\in S\rangle : \left(\prod_i x_i\right)^\infty$.
Typically a generating set of $L$ will be much smaller than any image of a minimal generating set of $J$. (Google for "Markov basis" to find tons of examples from algebraic statistics.) The proposition says that $J$ can be reconstructed from $L$, but also that whenever you remove a generator from $J$ and $L$ does not change, then the resulting ideal can not be prime (it has some extra components that are contained in the union of the coordinate planes). Dan's example is of this form.
Therefore the only chance that you may have, is when $J$ is, in fact, a complete intersection. This case is treated in the paper "Affine semigroup rings that are complete intersections" by Fischer, Morris, and Shapiro Proc. AMS 125 (11), 1997. It contains a combinatorial characterization complete intersection semigroups in Theorem 3.1 which may be useful for finding a counterexample in that case too.