No credit card required
Browse credit cards from a variety of issuers to see if there's a better card for you.
Someone with more experience then me may chime in, but he can check the pre-qual site for capital one or any of the various lenders to see if there are any offers available to him. Granted he could still be denied, but this will give you both a good idea of what is available.
I'd check the Capital One prequal page. From my research it seems Capital One is very forgiving in addition to being a good rebuild bank.
Capital ONe doesn't hold grudges. I was approved at 528 Fico and a Cap One charge off on my report. I would be very surprised if you would get turned down for Kohls card. Try Comenity SCT to get a card or two. Bank of America 99/500 is a good choice. If all else fails there is Fingerhut.
Talk to your own bank. My first back in the game was a $500 MC from my credit union. My scores were eh, they pushed it through for me because they knew I was trying to rebuild.
In terms of apping, I'd say the 2 AU cards he has are actually hurting him, as you said they are currently at high utilization. High utilization and apping for credit are not 2 things that go well together. High utilization often results in denials, or unfavorable (low limit, high APR) approvals. I'd strongly suggest against apping now, until utilization is in check. It's also financially an unwise move to take on more potential debt when the current debt load isn't being controlled or able to be paid off.
Another recommendation would be for him to take out a SSL. The SSL technique will give anyone that doesn't have a current open installment loan a 25-30 point boost to their FICO scores. This can be done with a SP and is easy for anyone to do, even with bad credit.
Unless there's something particularly handy about having the hubby as an AU on the Capital One cards, it might pay to remove him. They're not helping his chances of obtaining more credit at this point.
Also, if he could lower his Discover utilization just a wee bit — to 8.9% or below — he could see a scoring bump.
As others have said, check the Capital One pre-quals. If you see a definite interest rate rather than a wide range, I'd say he has a good chance.
I think he may pre-qualify for both the Platinum and QuicksilverOne cards. If that's the case, go for the Platinum. The Platinum has no rewards, but it's pretty easy to upgrade to a no-fee 1.5% rewards Quicksilver after a few months pass. While the QuicksilverOne offers rewards, it also has a fee. But most importantly, it's much more difficult to upgrade than the Platinum is.