I'm surprised amex didn't approve you. You look good to me, I guess it's just the short history. I don't travel enough to use any of the amex high fee charge cards. I have the blue cash everyday. I agree with the others about navy and if you want chase , consider the 5/24 rule.
Maybe some one else can comment, I'm not sure a charge card, like plat, builds credit as well as a credit card. Anyone?