Okay, this is a strange issue.

So, I have been working on an app for a very long time (before 3.0) and because I was using the Otto library I had to use the 3.0 SNAPSHOT.

It's all fine and the snapshot works great, and the app was released with the snapshot build. No worries, everything was working perfectly, so there was no concern about releasing a build with the snapshot.

So, I was working on an update for the app, and noticed that AA 3.0.1 had been released, so I figured I'd upgrade my snapshot to the official release.

Once again everything seemed to be working fine, so the update was released to the public.

After a day or so I started to receive feedback from some users complaining about "Invalid package file" when trying to download and install the update (both clean install, and as update).

Did some searching and found out that Google had previously fixed a Google Play error causing this specific error (back in august 2013 i believe). I did some more digging but nothing really turned up.

For a day or two I assumed that this was an error related to Google Play (faulty download, whatever), but I finally came across a device that had the same error. So I tried to debug it and see if LogCat could give me anything useful.

1362-1391/? E/PackageManager﹕ Package com.company.foo has mismatched uid: 10108 on disk, 10113 in settings
22989-22989/? E/dalvikvm﹕ LinearAlloc exceeded capacity (5242880), last=2272
22989-22989/? E/dalvikvm﹕ VM aborting
1259-1259/? E/installd﹕ dexopt failed on '/data/dalvik-cache/data@app@com.company.foo-1.apk@classes.dex' res = 11

More digging went to an issue in Android about "Deep interface hierarchies"
https://code.google.com/p/android/issues/detail?id=22586

Anyways, I all led to me downgrading the official 3.0.1 release to my prior SNAPSHOT build, and it started working for everyone again.

I am unsure if the implementation of AA have changed in order for the error to occur, or what else have happened.

Should be noted that the error only occurred on older devices running 2.3.3+ (not ICS devices)