Faits: A. A._ et B._ sont propriétaires de la parcelle n° 2369 du registre foncier de la commune de Travers (devenue commune de Val-de-Travers à la suite d'une fusion de communes le 1er janvier 2009) au lieu-dit les "Petites Lacherelles". En octobre 1991, ils ont obtenu l'autorisation de reconstruire sur cette parcelle, sise hors de la zone à bâtir, une ferme incendiée quelques années auparavant. Les plans mis à l'enquête mentionnaient un rural et un réduit. Le 2 mars 2005, ayant constaté qu'un atelier de serrurerie était installé dans la ferme en question, le Département de la gestion du territoire du canton de Neuchâtel (ci-après: le département) a imparti un délai à A._ pour demander un changement d'affectation de cet immeuble. A._ exploite par ailleurs une entreprise de serrurerie à Travers. Il a obtenu en 1998 l'autorisation d'implanter, à titre provisoire, un hangar sur la parcelle n° 2079. Le 26 mai 2000, le Conseil communal de Travers lui a ordonné de remettre les lieux en état avec un délai échéant au 31 juillet 2000. A._ a recouru contre cette décision auprès du département. Par décision du 23 février 2005, le département a accordé la dérogation nécessaire à la création d'un hangar sur la parcelle n° 2079 "à condition que A._ s'engage à y regrouper la majeure partie de son activité actuellement située aux Petites Lacherelles". B. Le 15 avril 2005, A._ et B._ ont déposé une demande de mise en conformité de l'atelier de serrurerie installé aux "Petites Lacherelles" sur la parcelle n° 2369. Durant la mise à l'enquête publique, les membres de l'hoirie X._ ainsi que D._ et C._, ont formé opposition. Par décision du 26 avril 2006, le département a admis les oppositions, refusé la dérogation et ordonné la remise en état des locaux "dans les trois mois qui sui[ven]t l'entrée en force de la présente décision". Le 29 mai 2006, la commune de Travers a formellement refusé le permis de construire et ordonné la remise en état des lieux conformément à la décision du 26 avril 2006. A._ et B._ ont recouru contre ces deux décisions auprès du Conseil d'Etat du canton de Neuchâtel, qui a rejeté les recours par décision du 21 novembre 2007. A._ et B._ ont alors contesté cette décision devant le Tribunal administratif du canton de Neuchâtel, Cour de droit public (ci-après: le Tribunal administratif). Leur recours a été rejeté par arrêt du 27 novembre 2008. Le Tribunal administratif a considéré en substance que l'atelier litigieux impliquait un changement complet d'affectation, que les conditions pour l'octroi d'une autorisation n'étaient pas remplies et que les recourants ne pouvaient bénéficier ni des règles sur la protection de la bonne foi ni de celles sur l'égalité de traitement. Enfin, il a estimé que l'autorité n'était pas déchue du droit d'exiger la remise en état, qui respectait le principe de la proportionnalité. C. Agissant par la voie du recours en matière de droit public, A._ et B._ demandent au Tribunal fédéral d'annuler cet arrêt. Ils se plaignent d'une violation de leur droit d'être entendus (art. 29 al. 2 Cst.), d'une appréciation arbitraire des preuves (art. 9 Cst.) ainsi que d'une violation des art. 24 et 24a de la loi fédérale sur l'aménagement du territoire du 22 juin 1979 (LAT; RS 700). Ils requièrent également l'octroi de l'effet suspensif. D._ et C._ ainsi que la commune de Val-de-Travers se sont déterminés; ils concluent au rejet du recours. Le Tribunal administratif conclut également au rejet du recours, en se référant aux considérants de son arrêt. L'Office fédéral du développement territorial a renoncé à présenter des observations. D. Par ordonnance du 2 février 2009, le Président de la Ire Cour de droit public a admis la requête d'effet suspensif. E. Le 1er mai 2009, A._ et B._, agissant seuls, ont présenté spontanément des observations complémentaires et déposé de nouvelles pièces. L'intimé D._ est décédé le 30 juin 2009. 