Yeah this is not a problem with the company. I ran into this problem after receiving my SSN for the first time. I informed the company I was working for that my social was still new so they might run into problems when running a background check. You need to do the work and get your social out there go to the bank and update your bank account with your social and get a credit card so you'll have some history. The company is in there complete right to not hire you if you can't meet there requirements. So I would talk to them and explain the sistuation.