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.

Considérant en droit:
1. Le jugement entrepris a été rendu en matière de rapports de travail de droit public au sens de l'art. 83 let. g LTF. Dans la mesure où la contestation porte sur l'annulation d'une décision de résiliation des rapports de travail, il s'agit d'une contestation de nature pécuniaire, de sorte que le motif d'exclusion de l'art. 83 let. g LTF n'entre pas en considération (voir par exemple les arrêts 8C_907/2010 du 8 juillet 2011 consid. 1 et 8C_170/2009 du 25 août 2009 consid. 1.1). La valeur litigieuse atteint par ailleurs le seuil de 15'000 fr. ouvrant la voie du recours en matière de droit public en ce domaine (art. 51 al. 2 et 85 al. 1 let. b LTF).
Pour le surplus, interjeté en temps utile (art. 100 al. 1 LTF) contre une décision finale (art. 90 LTF) prise en dernière instance cantonale (art. 86 al. 1 let. d LTF), le recours en matière de droit public est recevable.
2. Le Tribunal fédéral statue en principe sur la base des faits établis par l'autorité précédente (art. 105 al. 1 LTF), sous réserve des cas prévus à l'art. 105 al. 2 LTF. Le recourant ne peut critiquer la constatation des faits importants pour le jugement de la cause que si ceux-ci ont été établis en violation du droit au sens de l'art. 95 LTF ou de manière manifestement inexacte (art. 97 al. 1 LTF), c'est-à-dire arbitraire, ce qui lui appartient de démontrer par une argumentation répondant aux exigences de l'art. 42 al. 2 LTF, respectivement de l'art. 106 al. 2 LTF (<ref-ruling> consid. 4.3 p. 62; <ref-ruling> consid. 1.4.3 p. 254 s.).
Par ailleurs, sauf dans les cas prévus par l'art. 95 let. c à e LTF, qui n'entrent pas en considération en l'espèce, le Tribunal fédéral n'examine la mauvaise application du droit cantonal que si elle constitue une violation du droit fédéral (cf. art. 95 LTF) parce qu'elle est arbitraire au sens de l'art. 9 Cst. ou contraire à d'autres droits constitutionnels (<ref-ruling> consid. 1.3 p. 4; <ref-ruling> consid. 2.3 p. 466; <ref-ruling> consid. 1.2.1 p. 251).
3. 3.1 Le recourant voit une première violation de son droit d'être entendu dans le fait qu'il n'a pas été entendu avant le prononcé de la décision de résiliation, en ce sens que lors de leur entretien du 16 décembre 2010, le Chef du Département Z._ aurait déjà pris la décision de le licencier. Il en veut pour preuve le contenu du courriel adressé à son supérieur le 23 décembre 2010. Selon lui, la juridiction cantonale ne pouvait pas se retrancher derrière un argument formel, selon lequel c'est le Conseil d'Etat neuchâtelois et non pas le Chef du Département Z._ qui a prononcé la résiliation, puisque le gouvernement n'aurait fait qu'avaliser la décision de celui-ci. Par ailleurs, s'il fallait considérer, à la suite des premiers juges, que la décision de résiliation devait émaner du Conseil d'Etat, alors c'est également cette autorité qui aurait dû l'entendre; à défaut, son droit d'être entendu a été violé.
3.2 Tel qu'invoqué par le recourant et garanti par l'art. 29 al. 2 Cst., le droit d'être entendu comprend, en particulier, le droit pour la personne concernée de s'expliquer avant qu'une décision ne soit prise à son détriment (<ref-ruling> consid. 3.2 p. 494; <ref-ruling> consid. 2.2 p. 504 s., et les références). En matière de rapports de travail de droit public, des occasions relativement informelles de s'exprimer avant le licenciement peuvent remplir les exigences du droit constitutionnel d'être entendu, pour autant que la personne concernée ait compris qu'une telle mesure pouvait entrer en ligne de compte à son encontre (arrêts 1C_560/2008 du 6 avril 2009 et 1C_103/2007 du 7 décembre 2007 consid. 5.3). La personne concernée ne doit pas seulement connaître les faits qui lui sont reprochés, mais doit également savoir qu'une décision allant dans une certaine direction est envisagée à son égard (consid. 5.1 non publié aux <ref-ruling> de l'arrêt 8C_158/2009 du 2 septembre 2009 et les arrêts cités).
3.3 On ne saurait donner à l'échange de courriels entre le Chef du Département Z._ et le recourant des 23 et 25 décembre 2010 la portée que celui-ci lui accorde. La réponse du Conseiller d'Etat à la prise de position du recourant sur des alternatives relatives à sa situation apparemment discutées entre eux le 16 décembre 2010 montre que le Chef du Département Z._ n'avait pas "déjà pris la décision de le licencier", comme le prétend à tort le recourant. Le Conseiller d'Etat l'a en effet informé de son intention de reprendre "l'examen de cette situation après les Fêtes, soit au début du mois prochain", de sorte que l'issue n'en apparaissait nullement fixée. Par ailleurs, des quatre éventualités mentionnées par le recourant dans son courriel du 23 décembre 2010, seules deux d'entre elles (démission et convention de séparation) visaient la fin des rapports de service, alors que l'enquête administrative et la modification du cahier des charges du recourant n'allaient pas dans ce sens, de sorte que son argumentation tombe à faux.
En tant que le recourant se plaint ensuite de n'avoir pas été entendu par "la bonne autorité", son grief est mal fondé. L'art. 47 de la Loi neuchâteloise du 28 juin 1995 sur le statut de la fonction publique (LSt; RSN 152.510) prévoit qu'"avant de prendre sa décision [de renvoi pour justes motifs ou raisons graves], l'autorité de nomination entend l'intéressé en lui indiquant les faits ou omissions qui lui sont reprochés, ainsi que les moyens de défense dont il dispose, conformément à la loi sur la procédure et la juridiction administratives (LPJA), du 27 juin 1979, en particulier son droit de consulter le dossier et de se faire assister d'un mandataire". On rappellera dans ce contexte que ni la protection conférée par l'art. 29 al. 2 Cst. (<ref-ruling> consid. 5.3 p. 148; <ref-ruling> consid. 2.1 p. 428), ni celle prévue à l'art. 47 LSt (RJN 2004 p. 125 consid. 2) n'exigent que le droit d'être entendu de l'intéressé puisse être exercé oralement.
En l'occurrence, le recourant a été averti par courrier du 4 avril 2011, signé par le Chef du Département Z._, des reproches formulés à son encontre et de la mesure envisagée ("Intention de renvoi"). Un délai lui a par ailleurs été imparti pour s'exprimer sur la décision de renvoi entrant en ligne de compte, ce qu'il a fait en se déterminant les 15 et 29 avril 2011. Le recourant ne prétend pas, et aucun indice au dossier ne le laisse supposer, que le Conseil d'Etat neuchâtelois n'aurait pas pris connaissance du courrier du 4 avril 2011, ni examiné les déterminations y relatives de l'intéressé. Par conséquent, rien ne permet de douter que l'autorité de nomination a respecté le droit d'être entendu du recourant, puisqu'il a été informé des reproches à son égard, ainsi que du fait qu'une décision allant dans la direction d'une résiliation des rapports de service était envisagée, qu'il a pu s'exprimer à ce sujet et que le Conseil d'Etat a pris connaissance de cet échange de correspondances et des autres pièces du dossier avant de mettre un terme aux rapports de service.
4. 4.1 Invoquant une application arbitraire de l'art. 46 LSt., le recourant reproche à l'intimé d'avoir manqué de prononcer un avertissement préalable à son égard, comme le lui commandait cette disposition du droit cantonal. Il soutient que le rapport du Secrétaire général du Département Z._ (du 7 mai 2010), selon lequel il ne remplissait pas à satisfaction les exigences de sa fonction, aurait dû être alors suivi par un avertissement. Il se plaint aussi dans ce contexte d'un défaut de motivation du jugement entrepris, car les premiers juges n'auraient pas examiné son argumentation relative à l'obligation de lui notifier un avertissement bien avant son licenciement.
4.2 Sous le chapitre "Cessation des rapports de service" et le titre marginal "Renvoi pour justes motifs ou raisons graves", l'art. 45 al. 1 LSt a la teneur suivante: "Si des raisons d'inaptitude, de prestations insuffisantes, de manquements graves ou répétés aux devoirs de service ou d'autres raisons graves ne permettent plus la poursuite des rapports de service, l'autorité qui a nommé peut ordonner le renvoi d'un titulaire de fonction publique". La LSt prévoit cependant une procédure d'avertissement préalable à son art. 46 al. 1, selon lequel "lorsque les faits reprochés au titulaire de fonction publique dépendent de sa volonté ou lorsque les exigences de la fonction ne sont pas remplies à satisfaction, le chef de service doit en avertir par écrit l'intéressé après l'avoir entendu et lui fixer un délai raisonnable pour s'améliorer. Il lui en suggère autant que possible certains moyens".
Le but de l'avertissement est d'amender si possible l'intéressé (arrêt 2P.45/1998 du 28 mai 1998 consid. 3e). Il n'existe pas de critère absolu en matière d'avertissement, eu égard à la diversité des situations envisageables. La jurisprudence ne saurait poser de règles rigides sur le nombre et le contenu des avertissements dont la méconnaissance, par le travailleur, est susceptible de justifier un licenciement immédiat. Sont décisives, dans chaque cas particulier, entre autres circonstances, la nature, la gravité, la fréquence ou la durée des manquements reprochés au travailleur, de même que son attitude face aux injonctions, avertissements ou menaces formulées par l'employeur. Les juridictions cantonales disposent à cet égard d'un large pouvoir d'appréciation (arrêt 2P.163/2005 du 31 août 2005 consid. 7.1; cf. arrêt 8C_358/2009 du 8 mars 2010 consid. 4.3.1). En particulier, l'avertissement préalable prévu par l'art. 46 LSt n'est pas indispensable lorsque de justes motifs de renvoi sont fondés sur le seul intérêt du service (arrêt 2P.116/2006 du 16 août 2006).
4.3 Selon les premiers juges, la procédure de l'avertissement préalable n'est pas indispensable lorsque le seul intérêt du service motive le renvoi ou lorsque, compte tenu de la fonction en cause, de la nature des faits reprochés au titulaire et de la personnalité de celui-ci, on ne peut vraisemblablement pas s'attendre à ce que le comportement incriminé ou les prestations insuffisantes s'améliorent de manière à assurer durablement la bonne marche du service (RJN 2007 p. 218 consid. 6b). Ils ont constaté que la situation s'était en l'occurrence dégradée à l'intérieur de X._, laissant apparaître un malaise profond des collaborateurs qui se sentaient livrés à eux-mêmes, sans mission claire, ni objectif fixé. Alors que le recourant avait été requis par le chef du Département Z._ de "stabiliser la situation interne au service, en particulier les relations avec les collaborateurs-trices qui (lui) sont subordonnées-es" (lettre du 17 mai 2010), A._ n'était pas parvenu à s'imposer comme chef de service, la situation n'ayant pu être améliorée après des mois. Un avertissement plus formel n'aurait dès lors pas porter ses fruits.
En l'espèce, la motivation de l'autorité cantonale de recours n'apparaît pas insoutenable au regard de l'art. 46 LSt, dans la mesure où d'après ses constatations - qui ne sont pas en tant que telles remises en cause par le recourant -, A._ était inapte à gérer le service dont il avait la charge et n'avait pas été en mesure d'en améliorer la gestion malgré une injonction en ce sens de la part de son supérieur. Contrairement à ce que prétend le recourant, ce n'est pas sa réaction à la lecture du rapport du C._ qui lui était "largement reproché[e]", mais bien son inaptitude à assumer la responsabilité et la gestion du service en cause (incapacité à résoudre les conflits internes du service, absence de fixation d'objectif individuel à ses collaborateurs et de rigueur dans la ligne de conduite à imprimer à l'unité administrative, absence de maîtrise de son emploi du temps, incapacité à veiller au traitement et à la progression des dossiers dont il avait la responsabilité; cf. décision du 31 mai 2011). Compte tenu de la dégradation de la situation au sein du service en cause et du malaise profond qui y régnait sous la direction du recourant, l'autorité de nomination ne pouvait pas s'attendre à ce que le Chef de X._ améliore son comportement ou ses prestations; il s'agissait alors pour elle de prendre les dispositions nécessaires et dictées par l'intérêt du service, afin d'assurer dans l'immédiat et à long terme son bon fonctionnement et non pas d'obtenir du recourant qu'il corrige ou améliore son travail. On ajoutera que le supérieur du recourant s'est précisément entretenu avec lui des "problèmes que soul[evait] la marche actuelle de X._ et [de] leurs répercussions" en mai 2010 et a mis en évidence les affaires prioritaires (courrier du du 17 mai 2010). Pour le surplus, comme l'a constaté la juridiction cantonale, le recourant était conscient de la situation déficiente de son service, sans envisager de mesures concrètes pour la modifier, puisqu'il était prêt, en décembre 2010, à établir un projet de "convention de séparation" ou à se faire libérer des tâches de conduite du service (cf. courriel du 23 décembre 2010).
En conséquence, l'intimé pouvait se passer d'un avertissement formel au sens de l'art. 46 LSt.
4.4 En ce qui concerne l'argumentation du recourant relative au défaut de motivation du jugement entrepris, elle ne saurait pas non plus être suivie. Conformément à la jurisprudence sur le droit d'être entendu (<ref-ruling> consid. 4.1 p. 88; <ref-ruling> consid. 4.3 p. 540), la juridiction cantonale a en effet examiné le grief soulevé par le recourant en relation avec l'absence d'avertissement au sens de l'art. 46 LSt de façon suffisamment détaillée pour qu'il ait pu apprécier correctement la portée de la décision sur ce point et l'attaquer à bon escient, comme il ressort des arguments exposés dans son recours. Elle n'était par ailleurs pas tenue de discuter précisément tous les éléments de la motivation du recours, dès lors qu'elle a dûment expliqué les raisons pour lesquelles le renvoi du recourant pouvait à son avis être prononcé sans avertissement préalable.
5. Le recourant soulève encore une violation du droit d'être entendu sous l'aspect de son droit à faire administrer des preuves, au motif que les premiers juges ont refusé d'entendre plusieurs témoins dont il demandait l'audition, ainsi que de verser au dossier des pièces relatives à son adjoint et tous les projets qu'il avait élaborés et présentés au Chef et au Secrétaire général du Département Z._.
5.1 Le droit d'être entendu garanti par l'art. 29 al. 2 Cst. comprend le droit pour les parties de produire des preuves quant aux faits de nature à influer la décision et d'obtenir qu'il soit donné suite aux offres de preuves pertinentes (<ref-ruling> consid. 3.1 p. 370; <ref-ruling> consid. 2c p. 578; <ref-ruling> consid. 3a p. 436). En revanche, une partie n'a pas droit à l'administration d'une preuve dépourvue de pertinence parce qu'elle porte sur une circonstance sans rapport avec le litige, ou qu'une appréciation anticipée des preuves déjà recueillies démontre qu'elle ne serait pas de nature à emporter la conviction de la juridiction saisie (cf. ATF <ref-ruling> consid. 2.1 p. 429; <ref-ruling> consid. 6c/cc in fine p. 135). Comme le Tribunal fédéral est en principe lié par les faits constatés par la juridiction cantonale (consid. 2 supra), il ne revoit l'appréciation anticipée des preuves que sous l'angle restreint de l'arbitraire (<ref-ruling> consid. 3 p. 157; cf. également arrêt 8C_15/2009 du 11 janvier 2010 consid. 3.2).
5.2 Le recourant a demandé, en instance cantonale, la production du dossier concernant son adjoint qu'il avait remis à un juriste du service des ressources humaines de l'Etat de Neuchâtel, ainsi que l'audition de ce juriste. Il entendait ainsi démontrer que la tâche de "stabiliser la situation interne au service et à s'imposer comme Chef de service" lui avait été rendue impossible par la faute de son adjoint.
Il ressort des constatations de la juridiction cantonale que le service dont le recourant avait la charge connaissait des dysfonctionnements importants, qu'un malaise profond y régnait sous sa direction et qu'il n'avait pas été apte à en améliorer le fonctionnement, ni les relations avec les collaborateurs qui lui étaient subordonnés. C'est en vain que le recourant tente avec son offre de preuves de reporter sur son ancien adjoint la responsabilité d'une telle situation. Les premiers juges pouvaient en effet se dispenser d'établir l'éventuel rôle négatif que ce dernier aurait joué dans la dégradation de la situation, dès lors que l'inaptitude du recourant à assurer la direction de son service résultait des éléments du dossier. Les problèmes soulevés par la gestion de X._ ont ainsi fait l'objet de deux entretiens entre le Chef du Département Z._ et le recourant (cf. courrier du 17 mai 2010) et celui-ci a été invité à y remédier. Il est par ailleurs incontesté que le recourant n'est pas parvenu, alors qu'il assumait la direction et la responsabilité du service en cause, à remédier aux dysfonctionnements en question. Dès lors, en refusant de faire verser à la procédure le dossier relatif à B._, et à entendre le témoin invoqué, la juridiction cantonale n'a pas violé le droit d'être entendu du recourant.
5.3 A._ a encore requis l'audition de son prédécesseur, D._, à qui l'Etat de Neuchâtel aurait confié la responsabilité du dossier de Z._, afin de répondre au reproche principal selon lequel il aurait négligé ce projet. Cette offre de preuve n'est cependant pas pertinente. D'une part, contrairement à ce qu'allègue le recourant, la décision de renvoi du 31 mai 2011 n'est pas fondée sur la qualité de sa gestion du dossier de Z._ (celui-ci n'étant mentionné qu'en rapport avec la décision du recourant d'annuler une séance y relative), mais sur l'ensemble des dysfonctionnements de X._ dont il est à l'origine. En second lieu, il ressort de différentes pièces au dossier que le recourant était impliqué, en tant que chef de X._, dans le projet de réorganisation de Z._. Le Chef du Département Z._ lui a ainsi demandé de lui proposer "d'ici au 18 juin 2010, une structure provisoire pour Z._ qui soit dûment validée par les différents partenaires impliqués" (lettre du 17 mai 2010), ce qui contredit l'allégation du recourant relative à son absence de responsabilité dans le dossier en cause et rend inutile l'audition du témoin requise.
Enfin, la juridiction cantonale pouvait, sans arbitraire, renoncer à faire verser à la procédure l'ensemble des projets que le recourant avait élaborés et présentés à son supérieur (dont celui-ci demandait la production pour répondre à la critique d'un manque de rigueur dans la gestion de son service et du suivi administratif). Compte tenu des pièces au dossier, tels le courrier du Conseiller d'Etat du 17 mai 2010, un courriel du 15 avril 2010 du Secrétaire général du Département Z._ (qui fait état de problèmes, retards et dysfonctionnements internes de X._ énumérés par le chef de ce service) ou le rapport d'enquête administrative du 15 mars 2011, elle disposait en effet de suffisamment d'éléments établissant que le recourant n'était pas apte à assumer ses fonctions, ce qui justifiait de mettre un terme aux rapports de service. Du reste, le recourant ne tente pas, par une argumentation suffisamment précise, de démontrer le caractère arbitraire de l'appréciation des premiers juges, se limitant, par exemple, à qualifier de partiale et incomplète l'enquête administrative sans apporter ne serait-ce qu'un indice concret dans ce sens.
6. Il résulte de ce qui précède que les griefs du recourant sont mal fondés, de sorte que ses conclusions doivent être rejetées.
7. Le recourant supportera les frais judiciaires (art. 66 al. 1 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 3'000 fr., sont mis à la charge du recourant.
3. Le présent arrêt est communiqué aux parties et au Tribunal cantonal de la République et canton de Neuchâtel, Cour de droit public.
Lucerne, le 22 août 2012
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président: Ursprung
La Greffière: Moser-Szeless