I was wondering where you went!
I'll leave the technical info to loosie, she's the expert.
What you could try is making him "shoes" out of styrofoam, the kind that's used for insulating houses, and duct tape, to see if he's more comfortable with them on. It takes a little practice to make them, but it'll come
Cut a plate the size of the hoof out of the foam, then tape to foot.
If he gets more comfy, he'll move around more which in turn makes the hooves grow more, including the sole.
You'll have two possibilities, either go the barefoot way, which, IMO, is the better one, or go with orthopedic shoeing, which will, if done right, make him seem sound quicker, but, again, IMO, will pretty much mask the problem. Either way, it'll take time to grow a new, healthier hoof.
For possibilities of shoeing, NANRIC - Your Source for Equine Podiatry Products & Knowledge has tons of info, and might be helpful in finding a farrier who works that way.
It's a pretty bad start with a new horse, but im glad you stuck with him