Hi,
I have exactly the same problem.
It is after SP1 without a doubt.
For me the scenario is like this:
Redistribute or validate makes no difference at all.
If I completely remove the package/application it works.
Creating a brand new app/package also works but updating any "old" package/app it fails.
WOuld love to hear from anyone who has a solution to this.
Thanks