In this paper (arXiv:1407.1401) we quantize an N-dimensional classical Hamiltonian system that can be regarded as a deformation of the Coulomb problem. Moreover, the kinetic energy term in the Hamiltonian is just the one corresponding to an N-dimensional Taub-NUT space, a fact that makes this system relevant from a geometric viewpoint. Since the classical Hamiltonian is known to be maximally superintegrable, we propose a quantization prescription that preserves such superintegrability in the quantum mechanical setting. We show that, to this end, one must choose as the kinetic part of the Hamiltonian the conformal Laplacian of the underlying Riemannian manifold, which combines the usual Laplace-Beltrami operator on the Taub-NUT manifold and a multiple of its scalar curvature. As a consequence, we obtain a novel exactly solvable deformation of the quantum Coulomb problem, whose spectrum is computed in closed form, and showing that the well-known maximal degeneracy of the flat system is preserved in the deformed case. Several interesting algebraic and physical features of this new exactly solvable quantum system are analysed.