Complexity of linearized Ising model at 0
Not a full answer, but hopefully at least helpful. Computing the ground state of such an Ising Hamiltonian is NP-hard, as it contains Max-2-SAT, even if the couplings are restricted to $\pm J$. This is simply because if you take a 2-SAT instance, you can add the term $Jx_ix_j - Jx_ix_0 - J x_jx_0 = \mbox{daig}(-1,-1,-1,3)$ which is minimized iff $x_i \vee x_j$. Thus adding such terms to form a Hamiltonian will result in a spectrum where the ground state corresponds to the assignment of variables which maximizes the clauses satisfied as this corresponds to the maximum number of negative terms in the Hamiltonian. By adding an ancilla system it is then possible to create many such levels (via the tensor product of the two Hilbert spaces) with different energy levels. By tweaking the terms in the ancilla system, you can manipulate the absolute value of the energy levels corresponding to the ground state of the primary system and different excited states of the ancilla system. This would seem to indicate that the general problem is NP-hard. In the specific case of your question, you seem to fix J to be constant and positive which would seem to cause a problem with representing the negation of a variable in any of the clauses, and so this argument may not apply.

You may also be interested in cond-mat/0309240 for some results relating Ising lattices with various complexity classes. 

Hope this is useful.