This may or may not be relevant to your situation, but here's what the deal was with mine. I have CyanogenMod 7.1 installed, which puts dalvik-cache in the /cache partition instead of /data.
When you install apps from the Market, it downloads the .apk to /cache/downloads and installs it from there. If you don't have enough room in /cache/dalvik-cache for the installer to put the necessary files there, the install fails with a "package file is invalid" error.
There's nothing wrong with the package file at all. It's purely a matter of not having enough space in your /cache partition.
(forgive me if you see this exact same post in multiple places - if I'd known weeks ago that it wasn't really an "invalid package file" issue, it would've saved me a ton of useless googling - I'm just trying to spare others the same hassle)