I had this problem, too. I realized that the relays must be declared in your public Nostr profile. The clients I had been using only saved a private list of relays. I tried the Iris web client, and it lets you save relays publicly. Look for the purple button on this page: https://iris.to/settings/network