Was it being rejected for asking or for being broken if it didnt get the permissions?

Or was it simply not able to give a justifiable reason to Apple for needing the permission?

You say it was staying on device but once you have access to those contacts it would be trivial to add the ability to send them to a server or have them leak via third party tools like the facebook sdk. That would be completely invisible to the user after giving past permissions.

The fact that you say that the user experience is now worsened makes me believe that contact access was not an absolute requirement for the app to exist (like say... a contacts organizer or something) and is extra functionality.

Personally with very very few exceptions I will not grant an app access to my contacts since anyone in my contacts don't have the luxury to also consent to some company having their data.