All my contacts are stored on my Gmail account and will follow that. I suggest you do the same on your next phone if you didn't on this one. If your contacts were entered through your google account on a computer or on your phone as google contacts then you are fine. They will be already backed up and in your gmail account.
Otherwise the only thing I can think of is to try another store. I would think they should still be able to do it, but I don't know for sure.
Here. This. Now.
Get your own DropBox HERE!
"The young sow wild oats. The old grow sage." - Winston Churchill