Faits: A. Saisi d'une demande de prestations de l'assurance-invalidité présentée le 15 août 2005 par G._ (né en 1952), l'Office de l'assurance-invalidité du canton de Neuchâtel (ci-après: l'office AI) a recueilli différents avis médicaux, notamment du docteur U._, médecin-chef du Centre de psychiatrie gériatrique de l'Hôpital psychiatrique X._. Dans son rapport du 2 mars 2006, le médecin a fait état de troubles cognitifs essentiellement mnésiques et exécutifs et conclu que l'assuré n'était pas en mesure d'assumer une activité professionnelle. Par décision du 23 juin 2006, l'office AI a rejeté la demande de prestations. Après que G._ s'est opposé à ce prononcé et que le dossier a été complété par de nouveaux rapports médicaux, l'administration a confié une expertise au docteur O._, spécialiste FMH en neurologie. Dans son rapport du 11 juin 2009, l'expert a conclu que l'assuré ne présentait aucune affection neurologique ayant une répercussion sur sa capacité de travail comme nettoyeur - activité qu'il avait exercée jusqu'à fin février 2005 -, mais a relevé une discrète ataxie cérébelleuse probablement exogène et des troubles cognitifs sans correspondance organique significative. G._ a également été soumis à un examen auprès du docteur A._, spécialiste FMH en psychiatrie et psychothérapie, qui a diagnostiqué un trouble de conversion et un trouble dépressif majeur (épisode actuel moyen, chronique) sans répercussion sur la capacité de travail de l'intéressé (rapport du 18 décembre 2009). Fort de ces conclusions, l'office AI a rejeté l'opposition le 31 mai 2010, malgré un avis contraire du docteur U._ du 14 mai 2010. B. Statuant le 26 octobre 2011 sur le recours formé par G._ contre cette décision, le Tribunal cantonal du canton de Neuchâtel, Cour de droit public, l'a rejeté. C. G._ interjette un recours en matière de droit public contre ce jugement. Sous suite de frais et dépens, il conclut à l'annulation de celui-ci et de la décision du 31 mai 2010, ainsi que, à titre principal, à l'octroi d'une rente entière de l'assurance-invalidité à partir du 10 août 2006. Subsidiairement, il demande le renvoi du dossier (à la juridiction cantonale) pour complément d'instruction et/ou nouvelle décision au sens des considérants. L'office AI conclut au rejet du recours, tandis que l'Office fédéral des assurances sociales a renoncé à se déterminer à son sujet.