try logging on from your computer to make sure contacts are still on skype.
if you deleted them from your device at the beginning there is a good chance they have been deleted from your skype account as well