Bound state solutions (solitons) of nonlinear Schrödinger equations with a potential are investigated. Rigorous theory, asymptotic analysis, and direct computations elucidate the nature and magnitude of soliton instabilities in the semi-infinite spectral gap (first Brillouin zone). This is demonstrated with periodic, quasi-crystal, and other lattice-type structures. When the propagation constant bifurcates from the edge of the gap the soliton turns into a modulated Bloch-like wave. The ensuing structure and implications to collapse dynamics are investigated in detail.