I wonder, though. When you buy a new Android phone and sign in to Play, it downloads (or at least offers to) all the apps you had on your old phone. Does the same thing happen there
No, this particular exploit requires the malicious app be on a phone prior to an OS update. Additionally these apps would never* make it on the Play store as they have detectable characteristics (such as trying to use the same "Shared UID" of another app). In order to upload an app with the same Shared UID, you would need the same keystore to sign your app. Basically the way this bug works is exploiting the reverse of how the package manager grants precedence. The package manager give precedence to what is on the device first. So anything "updated" from the Play store, even if they spoofed the Shared UID and signature, would fail to install. The bug is that an app can "steal" the ability to control the permission completely, AND install itself or block the install of the legit version of an app.
So TL;DR: This definitely is a rather nasty privilege escalation bug in the package manager (if the paper is correct and I am reading it correctly), but one would likely need to side-load (or use a different app store) the malicious app prior to an OS update to get caught by it.
Agreed about permissions in general though. Personally I try not to give out contacts to any app unless they happen to be a type of "contact manager/replacement". Most apps can request a user use the default "contact picker" to add a contact, or share, or the like. No permission is required for this. The only reason apps request this is to prefill those "share with a friend" fields and to spam. This is similar to READ_PHONE_STATE, there are few legit reasons for an app to need this anymore. Apps can launch the dialer and prefill the number sans the permission, just not complete the call. They also have other ways to generate a UUID for the device without the IMEI, or the other info provided by READ_PHONE_STATE.
The USB storage permissions are antiquated, but not as sensitive. Apps do have private storage but this used to be quite limited in the earlier days of Android. The Nexus S was one of the first to come with a single, large internal storage (although even that was still partitioned). Prior to that you had a limited protected storage and an SD card. Nowadays they are adding better "Read" file permissions.
Finally, I think much of this stuff could be requested at time-of-use, rather than install. But they have to balance the "Are you sure you want to allow X?" disaster that was Windows UAC vs. sensible permissions. It is not as easy as it looks.
* (Well maybe not never, but very close to never...)