Faits: A. Le 21 mai 1999, les époux X._ ont acquis un bien-fonds de 2'125 m2, dont 155 sont occupés par une construction (habitation et garage), formant l'article zzz du cadastre de la commune de Cortaillod. La vente a été conclue au prix de 200 francs le m2. Selon le plan d'aménagement de la commune de Cortaillod du 26 septembre 1975, cette parcelle était affectée à la zone d'utilisation différée. Un nouveau plan d'aménagement et un nouveau règlement ont été adoptés par le Conseil général le 29 septembre 1995. Suite à leur sanction par le Conseil d'Etat le 27 octobre 1999 et à leur publication dans la Feuille officielle le 10 novembre 1999, la parcelle a été classée en zone d'habitation à faible densité 2. Par décision de plus-value du 21 février 2003, le Département cantonal de la gestion et du territoire (ci-après: le département cantonal) a fixé à 47'304 fr. 60 la contribution due par les époux X._ à la suite du changement d'affectation de leur parcelle. Sur recours des époux X._, le Tribunal administratif cantonal a annulé cette décision pour défaut de motivation et a renvoyé la cause au département cantonal pour instruction complémentaire et nouvelle décision. B. Par décision du 10 novembre 2004, le département cantonal a confirmé le prélèvement d'une plus-value dont il a fixé le montant à 40'268 fr. 60, sur la base du rapport de l'architecte qu'il avait mandaté. Les valeurs de référence retenues par l'expert pour le terrain avant et après le changement d'affectation, étaient respectivement de 3 francs le m2 (prix moyen du terrain agricole) et de 200 francs le m2. Les époux X._ ont recouru contre cette décision auprès du Tribunal administratif cantonal. Ce dernier l'a annulée, considérant que, quand bien même le changement d'affectation procurait un avantage aux époux X._, cela n'était pas suffisant pour constituer un avantage majeur au sens de l'art. 34 al. 1 LCAT. La mise en valeur du terrain dépendait en effet encore de l'adoption d'un plan de quartier et de l'accord d'un ou de plusieurs voisins, voire d'une réunion parcellaire par le biais d'une vente, ou d'un remembrement. C. Agissant par la voie du recours de droit administratif, le Conseil d'Etat du canton de Neuchâtel demande au Tribunal fédéral d'annuler l'arrêt du Tribunal administratif et de renvoyer l'affaire à cette juridiction pour nouvelle décision au sens des considérants. Le Tribunal administratif a renoncé à formuler des observations. Les époux X._ concluent au rejet du recours. L'Office fédéral du développement territorial a conclu à l'admission du recours. Il suggère de renvoyer la cause à la cour cantonale pour instruction complémentaire et nouvelle décision, cette dernière n'ayant pas élucidé à satisfaction de droit les préalables nécessaires à l'établissement du plan de quartier. Les époux X._ se sont déterminés sur les observations de l'Office fédéral, tandis que le Conseil d'Etat et le Tribunal administratif y ont renoncé.