I was in fact denied last week, not due to short credit history but because of my delinquencies in past (Auto Loan, CHASE CC, CapitalOne CC). I called the recon number and the lady over the phone was very nice. She asked me the reason of my delinquencies in past (Nov 2011) and also mentioned my delinquencies will drop off next 6 months. She then asked few more questions to verify identity and finally approved me with $500 CL. I know thats not much but something to start with. 4 months back i couldn't have imagined of applying for any credit anywhere.
She did mention one of the major reason of me getting approved is having a Checking & Savings account with them for over 2 years. CHASE valued the membership.
I would recommend CHASE as best to bank with. 2 years back when i was getting denied everywhere because of overdrafted accounts and being reported to CHEX system; CHASE was the one who gave me second chance and let me open CHASE Access checking. 6 months of good history they converted the account to Regular checking.
Sorry didn't mean to hijack the thread but just wanted to share some good experience with CHASE. I would say you hang on for one more year and will be treated really good by them. Meanwhile try to open a checking account there.