Yeah you either have to add the relays back or go back and follow all the accounts the were lost. This happens because the “following” event is published on certain relays, and if you remove the relay those events were published to, then those follows are removed from your contact list