Faits: A. A._ est l'administrateur de la société C._ SA, dont le but social est principalement l'exploitation d'un bureau technique de travaux d'architecture et d'ingénieur. Les 29 juillet et 21 octobre 2002, cette société a déposé au Conseil communal de X._ des demandes de sanction définitive relatives à des constructions sur ses articles 2676 et 2583 du cadastre de X._. Lors de la mise à l'enquête publique de ces projets, B._, propriétaire de l'article 2545 du cadastre de X._ et, par ailleurs, président de la commission d'urbanisme de la commune de X._, a fait opposition aux demandes de sanction présentées par C._ SA. Ces oppositions, déclarées irrecevables par le Conseil communal de X._ lors de ses décisions des 3 octobre 2002 et 27 mars 2003, ont donné lieu à une longue procédure. Alors que ces procédures étaient pendantes, A._ a adressé le 25 août 2003 au Conseil communal de X._ une lettre visant à dénoncer les actes de B._, ce dernier lui ayant proposé de retirer les oppositions contre le versement de 60'000 francs entre ses mains. Il s'est exprimé en ces termes: "(...) nous dénonçons vivement et publiquement: les actions téméraires et abusives de votre président de la commission d'urbanisme, élu démocratiquement, et qui essaie de nous extorquer CHF 60'000.-, preuve du 10 avril 2003 et dont vous étiez bien au courant depuis le 11 avril 2003 (...)". B. Le 12 septembre 2003, B._ a déposé une plainte pénale contre A._, notamment en raison de la lettre du 25 août 2003. Pour sa part, A._ a déposé le 12 décembre 2003 une plainte pénale à l'encontre de B._, pour calomnie, menace et contrainte. Le Ministère public neuchâtelois a suspendu cette plainte jusqu'à droit connu dans la procédure pénale à l'encontre du plaignant. C. Par jugement du 4 novembre 2005, le Tribunal de police du district de Boudry a condamné A._, pour diffamation et pour violation des dispositions relatives à la protection de l'environnement, à une amende de 5'000 francs, avec un délai de radiation de deux ans, aux frais de justice arrêtés à 1'723 francs et au versement d'une indemnité de dépens de 750 francs en faveur de B._. En droit, le tribunal a considéré, s'agissant de l'infraction de diffamation, que A._ n'avait pas apporté la preuve de la vérité selon l'art. 173 ch. 2 CP, puisqu'aucun jugement pénal ne condamnait B._ pour extorsion. En conséquence, il a condamné A._ pour diffamation. D. Par arrêt du 16 mars 2006, la Cour de cassation pénale du Tribunal cantonal du canton de Neuchâtel a admis le pourvoi en cassation déposé par A._, en ce sens qu'elle l'a libéré de la condamnation pour violation des dispositions relatives à la protection de l'environnement. Statuant elle-même, elle a condamné A._ à une amende de 4'200 francs, fixant à deux ans le délai de radiation. Elle a réduit à 1'550 francs les frais de justice de première instance et a fixé à 750 francs l'indemnité de dépens pour la première instance. Enfin, elle a condamné A._ à une part réduite des frais de deuxième instance, arrêtés à 660 francs. En droit, elle a constaté, en relation avec l'infraction de diffamation, que A._ avait adressé la lettre litigieuse au Conseil communal de X._, alors que celui-ci avait déjà déclaré irrecevable l'opposition de B._ au projet de construction de C._ SA et que le litige était pendant devant le Tribunal administratif neuchâtelois. Elle en a déduit que A._ ne pouvait poursuivre ni un intérêt public ni un intérêt privé digne de protection en dévoilant au conseil communal les manoeuvres de B._, mais ne pouvait avoir adressé la lettre litigieuse que par vengeance, pour dire du mal de B._. En conformité avec l'art. 173 ch. 3 CP, A._ ne pouvait donc être admis à faire la preuve de la vérité selon l'art. 173 ch. 2 CP. La cour cantonale a ainsi maintenu la condamnation pour diffamation par substitution de motifs. E. Contre cet arrêt cantonal, A._ dépose un pourvoi en nullité devant le Tribunal fédéral. Il conclut à l'annulation de l'arrêt attaqué, soutenant qu'il aurait dû être autorisé à faire la preuve de la vérité et que cette preuve avait été apportée, en l'absence de jugement de condamnation, par le biais de divers indices. L'intimé ainsi que le Ministère public et le Tribunal cantonal neuchâtelois ont renoncé à se déterminer.