They would have to get the base distribution signing key, which is probably a shared secret that requires multiple people to unlock.
Have there been any hints of NSLs or FISC orders requiring the disclosure of private Linux distribution keys, some of which may not even be held in the US?
So, since they don't specifically need to patch your openssl package to compromise your openssl library, they could just as well suborn the signing key of (presuming Ubuntu) some PPA author, as long as the user they're trying to bug has that PPA in their sources.list.
Packaging systems do detect file collisions, however, and with something vaguely similar to checkinstall or fakeroot they could detect attempts to overwrite other packages' files in the pre- and post-install scripts.
http://www.oracle.com/technetwork/server-storage/solaris11/t...
That coupled with system wide snapshots is a great tool to audit a system after a patch is applied.