If you restored As a New Phone and not from a backup then I'd guess you just need to reload your cydia sources. (Look for More Package Sources or something like that in Cydia.) In the future you can probably avoid these kinds of issues by not installing software to steal apps.