It is necessary, but it is not sufficient. All cost sharing (except for mandated preventive at no cost sharing) must also take place after the deductible. Another way to state that: the plan can pay nothing except for preventive care before the deductible is met. For example, you can have a plan that meets the criteria for deductible and out-of-pocket maximum amounts (say $1500 deductible and $4000 OOP max) but has generic prescriptions that are covered at $10 copay and not subject to the deductible. That plan would not be HSA eligible. This is the most common reason that an otherwise eligible plan would not be eligible.
For family plans, the deductible must be structured in a way that no services are paid before the family deductible, even what would be the individual deductible has been reached. For example, say you have a plan that has a $1300 individual deductible and $2600 family deductible. If a single person on a family plan has a large claim, then the he is subject to the $2600 deductible (this is not always the case for non-HSA plans).