The Cosmological Constant Problem is re-examined in terms of the minimal principles of unitarity and special relativity, and in terms of our present experimental understanding. This analysis brings to light a loop-hole in the usual derivation of the problem, which can be termed "graviton compositeness". Such compositeness is very tightly constrained theoretically by unitarity and Lorentz invariance, although string theory provides a striking example. It is speculated that graviton compositeness is responsible for resolving the Cosmological Constant Problem, in which case its experimental signature will be a drastic departure from Newton's Law in sub-millimeter tests of gravity.