That doesn't work as well for auto-discovery of other Signal users, though. The latter enables auto-discovery based on people whose phone numbers are already in one's contact books. With the former, one needs to collect other people's usernames. It's not a tough thing to do, but it does make auto-discovery difficult.
It does if one's Contacts app stores Signal contact information for one's contacts; then one could simply query using non-Signal information as the key (e.g. one could ask, 'give me Signal contact information for tel:+15551212, mailto:fizzbuzz@barquux.org and http://plus.google.com/SomeUserName').
That doesn't seem like a very good tradeoff because then it requires Signal to store/compare _more_ personally identifying information (though I guess you could make many of those things pseudo-anonymous).
Actually, it's possible to do even better that that: one can execute a private set intersection protocol so that you & each of your contacts can discover mutual contacts without revealing others.
Signal aren't required to store any personally identifying information: they choose to do so.