We study, via the replica method of disordered systems, the packing problem of hard-spheres with a square-well attractive potential when the space dimensionality, d, becomes infinitely large. The phase diagram of the system exhibits reentrancy of the liquid-glass transition line, two distinct glass states and a glass-to-glass transition, much similar to what has been previously obtained by Mode-Coupling Theory, numerical simulations and experiments. The presence of the phase reentrance implies that for a suitable choice of the intensity and attraction range, high-density sphere packings more compact than the one corresponding to pure hard-spheres can be constructed in polynomial time in the number of particles (at fixed, large d) for packing fractions smaller than 6.5 d 2^{-d}. Although our derivation is not a formal mathematical proof, we believe it meets the standards of rigor of theoretical physics, and at this level of rigor it provides a small improvement of the lower bound on the sphere packing problem. ; Comment: 18 pages, 7 figures -- Proceedings of the International Meeting on "Inference, Computation, and Spin Glasses", Sapporo, Japan, July 28-30, 2013