Have you tried your local credit union? Credit Unions are much more sympathetic and easier to work with.
if denied go with hsbc\ orchard and try again in 6 months.
Hotsaka has it right. Orchard approved me for their secured product when Citi denied me for a secured card when I started building credit. I have no complaints about Orchard, they have been easy to make payments on and do not report as secured on the credit reports. You can pay them online, and it is free to do so. (Some banks and CC's charge to make online payments.)
Only bad thing about Orchard is it might take forever to unsecure.
Hmmm, I was gonna do the Orchard bank card for him but there might be a problem... On his credit report he has a collection listed from best buy that says HSBC/best buy. Is it the same thing? If so I bet they wouldn't approve him for the card considering he owes them money. I'm confused tho, cuz the card was a best buy card. I dunno, should I try it or not?