<< Got rejected today, they citied insuffiencent credit information >>
What other credit cards do you have? You're going to need at least a year of good credit (err earning it through paying bills on time, etc) to be approved for one. Once you start getting pre-approved apps in the mail asking you to sign up for every Platinum/Gold Visa/Mastercard credit card there is, you're credit is pretty solid and you'll have an excellent chance of getting approved. 
I myself applied before Christmas and just got mine yesterday. (I'm a little pissed I missed out on all the goodies...mostly the 30% off @ Virgin) I've had 4 credit cards, 2 dating back to 11/1999 (canceled), one dating back to April 00, one to October 00, all payments paid in full on time, I guess that looked good in their eyes.