I was able to restore the threaded view (AllItems.aspx) back but using FrontPage.
This is what I did, I changed the default view to Flat view on a discussion board. Then I was able to deleted the threaded view ( like the user in your company deleted).
Then I created a new discussion board and using FrontPage I copied the AllItems.aspx page and pasted within the old one. Then I had to change the List GUID on the AllItems.aspx page. When you click "Modify settings and columns" you will get the list ID number on the address bar, example
List={8A15BA2D-6F15-4202-BF9A-4A8AADB1A0DB}
Put the ID of the old discussion board in AllItems.aspx file and you will have the Threaded view back, later you can make this view as the default one.
But this is using FrontPage.