As of 4/1/2015, I do not believe there is a way to do this.
Plus, if you use the "Replace Document" feature on the Document, customers will not get the new logo at all when upgrading.
The best workaround I could come up with was to create a 2nd Document and assign it to the App. New customers will get the new logo automatically on install. Existing customers will get the new Document on package upgrade, but the App will still have the old logo. They can however change the logo on the App manually.
I realize this is not ideal, but it was the best workaround I could come up with given the current state of the platform.
If you really wanted to get tricky you might be able to schedule some Apex code to run on package installation that updates the CustomApp logo... It appears the only way to do this through the Metadata API. Again, this does not seem to be natively supported by the platform, but others have figured out ways to make it happen:
Your mileage may vary. I did not go this route due to it being overly complicated and this being a "nice to have" vs mandatory for me.