Workout routines were not deleted, they were removed from the Favorites list. You can still access these routines through <i>Home > Routines</i>.

To delete a custom routine permanently, first open it (it is "opened" when you see the list of exercises that make that routine), then tap the <font color=red><b>-</b></font> button in the navigation bar at the top of the page.