When the user story was deleted, the defect would not have been deleted with it. What happens is, that we put the user story into the recycle bin and remove the connection to the defect. On restoring the story the link will not be restored. You can check in the revision history of the user story, which defect it was, so that you can associate it again. You will see an entry like the following in the revision history:
Moved to Recycle Bin, DEFECTS removed [DExxx: Name of defect], DEFECT STATUS changed from [NONE_CLOSED] to [NONE]
To see the Revision history of the story, open the story detail page and then click on the tab "Revisions".