One of the issues that we always see when creating new releases of our managed package is that new or changed picklist values don't deploy when someone upgrades our app using a new release that we just cut. We have to provide instructions on going into the object and updating the picklist values manually.
How are other managing this? Is there a better way? Am I missing something?