Faits: A. A.a Par testament olographe du 25 avril 2002, X._, veuf et sans enfant, a attribué son immeuble de D._ à la commune de C._ et celui abritant le restaurant Y._ à A._. A.b En raison d'une grave maladie, le disposant a été hospitalisé le 14 juillet 2003 et a subi une intervention chirurgicale le 22 juillet suivant, pratiquée par le Dr B._. Le jour même, le disposant a souhaité voir son notaire. Celui-ci étant en vacances, le disposant a rencontré Me E._ le 24 juillet et lui a expliqué vouloir modifier son testament, en ce sens qu'il ne voulait plus attribuer l'auberge de Y._ à A._, mais à la commune de C._, et ne plus remettre l'immeuble de D._ à celle-ci, mais à son médecin. Le notaire a cru identifier le médecin de son client en la personne du Dr F._. Il a alors préparé un projet de testament authentique qu'il a présenté au disposant. Ce dernier a confirmé le contenu de l'acte et l'a signé le 25 juillet 2003. A.c Le disposant est décédé le 31 juillet 2003 à l'hôpital de G._. Après avoir notifié le testament authentique aux bénéficiaires désignés, l'exécuteur testamentaire a informé le Président du Tribunal de district, le 26 août 2003, que le Dr F._ ne connaissait nullement le disposant, à l'inverse du Dr B._ qui a déclaré que le disposant lui avait promis son immeuble de D._. Au cours du mois suivant, A._, la commune de C._ et le Dr B._ se sont opposés à la délivrance d'un certificat d'hérédité. B. B.a Le 8 juillet 2004, la commune de C._ a ouvert action contre le Dr F._ en nullité du testament du 25 juillet 2003 devant la IIe Cour civile du Tribunal cantonal du canton de Neuchâtel. A._ a fait de même le 9 juillet 2004 contre la commune de C._ et le Dr F._. La jonction de ces causes a été ordonnée. La commune de C._ a acquiescé aux conclusions prises par A._. B.b Le 20 août 2004, le Dr B._ a ouvert action en rectification du testament authentique, contre le Dr F._ uniquement, devant la IIe Cour civile du Tribunal cantonal du canton de Neuchâtel. Cette cause a été suspendue jusqu'à droit connu sur la validité dudit testament. B.c Le 26 janvier 2005, le Dr F._ a acquiescé aux conclusions de A._ et de la commune de C._ dans les deux actions ouvertes contre lui en nullité du testament authentique. Il a ensuite requis le classement de la procédure de rectification de ce testament. Le Dr B._ a conclu au rejet de la requête de classement. Le 23 mai 2005, il a déposé trois mémoires de tierce opposition contre les acquiescements de la commune de C._ et du Dr F._. B.d Statuant le 1er février 2010 sur la demande de rectification du testament, la IIe Cour civile du Tribunal cantonal du canton de Neuchâtel a déclaré irrecevables les conclusions reconventionnelles de la commune de C._ et du Dr F._ en nullité du testament authentique. Elle a en outre rectifié l'institution d'héritier en remplaçant le nom du Dr F._ par celui du Dr B._. Le 7 juin 2010, l'intimé s'est désisté des instances de tierce opposition. B.e Le 12 mai 2010, A._ a ouvert action contre le Dr B._ en nullité du testament authentique du 25 juillet 2003 devant la IIe Cour civile du Tribunal cantonal du canton de Neuchâtel. Par jugement du 29 décembre 2010 expédié aux parties le lendemain, les juges cantonaux ont déclaré l'action du recourant "irrecevable" en raison de la péremption de son action. C. Par acte du 1er février 2011, A._ a interjeté un recours en matière civile au Tribunal fédéral. Il conclut principalement à l'annulation du jugement entrepris et à sa réforme en ce sens que l'action en nullité du testament n'est pas périmée. Subsidiairement, il conclut au renvoi de la cause à l'autorité de première instance pour nouvelle décision. Par ordonnance du 3 février 2011, la Présidente de la IIe Cour de droit civil du Tribunal fédéral a refusé l'effet suspensif au recours. Invités à se déterminer, l'intimé conclut au rejet du recours et l'autorité cantonale se réfère aux considérants de son jugement. 