Faits: A. Par arrêté du Conseil d'Etat neuchâtelois du 22 avril 2009, A._ a été nommé chef du Service X._, rattaché au Département neuchâtelois Z._, à partir du 1er septembre 2009. Dans une note du 7 mai 2010 adressée au Conseiller d'Etat et chef du Département Z._, le Secrétaire général dudit département a fait état de problèmes au sein de X._, relatifs à l'avancement de certains projets, à des conflits de personnes, à l'absence réitérée du Chef de X._ et aux relations "exécrables" que celui-ci entretenait avec son adjoint, B._. Après avoir eu deux entretiens avec A._, au cours desquels les problèmes mentionnés ont été abordés, du moins en partie, le Chef du Département Z._ lui a indiqué ce qu'il attendait de lui et l'a invité à porter une attention toute particulière sur diverses urgences (dont la stabilisation de la situation interne de X._; courrier du 17 mai 2010). A la suite d'une nouvelle discussion qu'il a eue le 16 décembre 2010 avec le Conseiller d'Etat, A._ a pris position, par courriel du 23 décembre suivant, sur quatre éventualités concernant sa situation (démission, enquête administrative, convention de séparation et libération des tâches de conduite du service avec maintien à la présidence de l'organe cantonal Z._. Le 18 janvier 2011, le Chef du Département Z._ a chargé C._, ancien commandant de la police cantonale neuchâteloise, de mener une enquête administrative sur X._. Le 10 mars suivant, C._ s'est entretenu avec A._ du résultat de son enquête et lui a fait part de ses observations. Le 22 mars 2011, le Secrétaire général du Département Z._ a interrompu une séance de travail à laquelle participait A._ et annulé une séance prévue ultérieurement, en raison du comportement de celui-ci, respectivement de son manque de préparation. Deux jours plus tard, il a été informé par C._ que, selon ce qui lui avait été rapporté, A._ avait menacé ses collaborateurs de plainte pénale au vu du contenu des procès-verbaux de leur audition lors de l'enquête administrative, dont il affirmait avoir eu connaissance. Par courrier du 4 avril 2011 (intitulé "Intention de renvoi, droit d'être entendu [Art. 45ss LSt]"), le Conseiller d'Etat a annoncé à A._ qu'une résiliation des rapports de travail était envisagée, dès lors que la bonne marche de X._ n'était plus assurée et que la confiance à son égard lui paraissait rompue; il lui a par ailleurs imparti un délai dans lequel il l'invitait à s'exprimer sur la décision de renvoi envisagée. L'intéressé s'est déterminé les 15 et 29 avril 2011. Par décision du 31 mai 2011, le Conseil d'Etat neuchâtelois a mis fin aux rapports de service de A._ avec effet au 31 août suivant, motif pris, notamment, de la rupture définitive de la confiance en ses capacités à conduire X._ et à en gérer le personnel. B. A._ a recouru contre cette décision au Tribunal cantonal de la République et canton de Neuchâtel, Cour de droit public, qui l'a débouté par jugement du 21 mars 2012. C. Agissant par la voie du recours en matière de droit public, A._ demande au Tribunal fédéral d'annuler ce jugement et la décision du Conseil d'Etat du 31 mai 2011, sous suite de frais et dépens. Il requiert par ailleurs que l'effet suspensif soit octroyé à son recours, ce qui lui a été refusé par ordonnance du 19 juillet 2012. Le Gouvernement neuchâtelois conclut au rejet du recours dans la mesure où il est recevable. 