Did you actually receive the rejection letter? It sounds like you did, but I was unsure. If I understood correctly, they state their reasoning as "unable to verify identity" and yet, when you called them after receiving the letter, they did not give you any options to actually try "proving" your identity?
I have been through the same issue with Synchrony. As mentioned above, you should check your LexisNexis Consumer Report. I see that you have already checked with the 3 major credit bureaus, but it is important that you at least check with LN, if not more from other secondary companies like ARS and Innovis. I learned my lesson the hard way recently.
You just got your 1st card. Quicksilver is a good card, but like mentioned above, it may be a bucketed card, which means it has virtually no room for further growth in its credit limit. I would concentrate all your spending on this 1 card for now, at least 6 months if not more. In the meantime, you can still use your VISA debit card at Costco. Or if you are willing, you can buy Costco Shop card online with your QS first beforehand and use that at the register.
Since you only have 1 card, I would leave a very tiny amount report every month, while making necessary payments early before the statement end date, so that you can free up more credit for your monthly spending needs. Go over your expenses and see where you are spending the most, and determine the most important categories to you, so that you know exactly what kind of rewards cards will actually become useful to you instead of just applying for anything that "looks good at first glance."
