Managed Package Permission Set missing permissions

you were dead on - when I looked up the issue, I found that you were creating a dependency on the Campaign standard object.

Unfortunately, we don't have the ability to break containment of a package to set permissions on things that aren't in the package (like Campaigns).

We have discussed this issue internally and are trying to work out a way to allow this through the various install and upgrade paths where admins are aware that you may be giving access to something that is not explicitly defined in the package. It's not an easy problem to solve technically or functionally but we know it's important to address it so that you can continue to build applications on top of standard [CRM] functionality.

There is an idea on ideaexchange around this: https://success.salesforce.com/ideaView?id=08730000000kmm6AAA - please comment, vote, and evangelize this to other members of the community.

There is a work around. You can define a lookup relationship to the Campaign object (lookup doesn't require the antecedent permission). You can then use the post install apex script functionality to create a new permission set with access to the standard object. This is sub-optimal for a number of different reasons but may help provide your subscriber with the access to campaigns that you may need.

It's not wholesale upload of the permission set. It follows the same rules as the migration tool. Only objects and fields in the change set are uploaded. This allows partial updates to profiles and permission sets. You must include all appropriate entities, even if they're not changing directly.