If you have access to the general VCAST program, you'll want to download Back-Up Assistant and run it.
It's ludicrous that the store told you they would charge you $35 to transfer contacts, especially considering you're already a customer...I'd talk to a manager/supervisor about this if I were you.
If your phone is truly a dated dumb-phone, and you can't access the program, than you will have to manually input contacts into the "X". If you have to go this route, I'd start saving them to a Gmail account.