Yes, all objects were valid, I checked that. What I thought of is that the "existing state" of a package (held in the PGA?) may get invalid if referenced objects are modified. If I remember correctly, this cached invalid state is not refreshed automatically by the Oracle Server.
However, I tried...