It seems the package is invalid. Check for user grants on the package, synonyms, all that stuff. If it runs on the second try it is being re-compiled at run time, so it may not exactly exist in the runtime (user) schema. ust a thought, but it is a place to look.