Faits:
A. A.a M._ a travaillé en Suisse du 15 septembre 1987 au 29 juillet 1996 en qualité de maçon pour le compte de l'entreprise X._ SA. Le 15 novembre 1996, l'intéressé a déposé une demande de prestations auprès de l'office AI du Valais (ci-après: l'office AI).
Dans le cadre de l'instruction de la demande, l'office AI a mandaté d'une part le docteur O._, spécialiste FMH en médecine physique, réhabilitation et maladies rhumatismales et médecin-chef à l'Hôpital de Y._ et d'autre part, le docteur N._, spécialiste FMH en psychiatrie et psychothérapie. Dans son rapport du 29 octobre 1998, le docteur O._ a posé le diagnostic de fibromyalgie, de lombalgies sur arthrose facettaire postérieure L4-L5, de hernie paramédiane gauche L5-S1 asymptomatique et de céphalées occipito-frontales droites d'étiologie tensionnelle. Il a conclu à une incapacité de travail complète en tant que maçon. En revanche, dans une activité adaptée légère, ne nécessitant pas le port de charges de plus de 10 kilos, l'assuré disposait, sur le plan somatique, d'une capacité résiduelle de travail de 70 % au moins. Dans son rapport d'expertise du 18 décembre 1999, le docteur N._ a fait état d'un trouble douloureux chronique associant à la fois des causes somatiques et psychologiques et un trouble de la personnalité non spécifique. Il a indiqué qu'en tenant compte uniquement des éléments psychiatriques, il y avait lieu de reconnaître à l'assuré une incapacité de travail de 70 %.
Se fondant sur les conclusions des expertises précitées, l'office AI a retenu que l'assuré disposait d'une capacité résiduelle de travail de 30 % dans une activité adaptée. La comparaison entre le revenu qu'il pouvait réaliser dans une telle activité avec celui qui aurait été le sien dans sa profession de maçon, laissait apparaître une perte de gain de 80 %. Aussi, par décision du 17 mars 2000, l'office AI a alloué à M._ une rente entière fondée sur un degré d'invalidité de 80 %, à partir du 1er janvier 1997.
A.b En janvier 2003, l'office de l'assurance-invalidité pour les assurés résidant à l'étranger (ci-après: l'OAIE) a entrepris une procédure de révision du droit à la rente de l'assuré. A cet effet, il a recueilli divers renseignements médicaux, à savoir un rapport du 1er mars 2004, du docteur H._ (psychiatre), lequel atteste l'absence de pathologie psychiatrique justifiant une incapacité de travail, le formulaire E 213 du 11 mars 2004, de l'Institut portugais de solidarité et de sécurité sociale (ISSS), dont il ressort que l'assuré pourrait exercer à plein temps une activité adaptée à son état de santé, et un rapport du 3 décembre 2004 de la doctoresse S._, médecin traitant, laquelle a fait état de lombalgies empêchant l'exercice de son ancienne activité de maçon ainsi que de céphalées, d'hypertension artérielle, d'une dyslipidémie et d'un état dépressif.
L'OAIE a soumis le cas à son médecin-conseil, la doctoresse E._, laquelle a considéré que dans l'activité de maçon, l'incapacité de travail restait de 70 %. En revanche, celle-ci n'était que de 30 % dans une activité plus légère, essentiellement assise, sans port de charges lourdes (cf. rapports des 28 juillet 2004 et 2 mars 2005). Se fondant sur les conclusions de ce médecin, l'OAIE a procédé à un nouveau calcul du degré d'invalidité de l'assuré (44 %). Par décision du 14 mars 2005, il a ainsi supprimé le droit à une rente entière et l'a remplacé par le droit à un quart de rente d'invalidité à partir du 1er mai 2005.
M._ a formé opposition contre cette décision à l'appui de laquelle il a produit deux rapport médicaux, l'un du docteur U._, spécialiste FMH en chirurgie orthopédique, du 3 mai 2005, et l'autre du docteur D._, spécialiste FMH en neurologie, du 20 juin 2005.
Par décision sur opposition du 22 août 2005, l'OAIE a confirmé sa décision du 14 mars 2005.
B. M._ a recouru contre cette décision sur opposition devant la Commission fédérale de recours en matière d'AVS/AI pour les personnes résidant à l'étranger (aujourd'hui: Tribunal administratif fédéral) en concluant à l'octroi d'une rente fondée sur un degré d'invalidité de 75 % au moins. Il a en outre demandé que les frais d'expertises soient mis à la charge de l'OAIE pour un montant total de 664 fr.
Par arrêt du 4 juin 2007, le Tribunal administratif fédéral a rejeté le recours.
C. M._ interjette un recours en matière de droit public contre cet arrêt dont il demande l'annulation. Il conclut, sous suite de frais et dépens, à l'octroi d'une rente fondée sur un taux d'invalidité de 50 % ainsi qu'à la prise en charge des frais d'expertises privées. L'intimé conclut au rejet du recours, tandis que l'Office fédéral des assurances sociales ne s'est pas déterminé.
Considérant en droit:
1. Le recours en matière de droit public peut être formé notamment pour violation du droit fédéral (art. 95 let. a LTF), que le Tribunal fédéral applique d'office (art. 106 al. 1 LTF), n'étant ainsi limité ni par les arguments du recourant, ni par la motivation de l'autorité précédente (cf. ATF 130 III 136 consid. 1.4 p. 140). Le Tribunal fédéral n'examine en principe que les griefs invoqués, compte tenu de l'exigence de motivation prévue à l'art. 42 al. 2 LTF et ne peut aller au-delà des conclusions des parties (art. 107 al. 1 LTF). Il fonde son raisonnement sur les faits retenus par la juridiction de première instance (art. 105 al. 1 LTF) sauf s'ils ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'art. 95 LTF (art. 105 al. 2 LTF). Le recourant qui entend s'écarter des faits constatés doit expliquer de manière circonstanciée en quoi les conditions de l'art. 105 al. 2 LTF sont réalisées, sinon un état de fait divergent ne peut être pris en considération. Aucun fait nouveau ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente (art. 99 al. 1 LTF).
2. En l'espèce, il s'agit de savoir si l'on est en présence d'un motif de révision, ce qui suppose une modification notable du taux d'invalidité (art. 17 LPGA). A cet égard, le jugement entrepris expose correctement les règles légales et les principes jurisprudentiels relatifs à l'évaluation de l'invalidité et de la révision de la rente. Il suffit d'y renvoyer sur ce point.
3. Les premiers juges ont constaté qu'une rente entière d'invalidité avait été octroyée au recourant principalement en raison de troubles psychiques. Lors de la procédure de révision du droit à la rente, l'intimé avait versé au dossier le rapport du psychiatre H._, lequel attestait l'absence de tout trouble psychopathologique chez l'assuré. Ce dernier ne contestait d'ailleurs pas le fait que son état de santé s'était amélioré sur le plan psychique. Au vu de ces éléments, les premiers juges ont conclu que d'un point de vue psychiatrique, les atteintes à la santé du recourant avaient disparu et ne justifiaient plus d'incapacité de travail.
Dans son recours en matière de droit public, le recourant ne conteste pas l'absence de troubles psychiques constatée par les juges de première instance. En revanche, il s'en prend à l'appréciation des preuves par l'autorité judiciaire précédente en ce qui concerne son état de santé sur le plan somatique.
4. 4.1 Sur le plan somatique, les premiers juges ont constaté, en se fondant sur les rapports d'expertise des docteurs U._ et D._, que l'état de santé du recourant n'avait pas évolué. En particulier, il ne s'était pas aggravé en raison des céphalées. Comme le retient la juridiction cantonale, si l'on compare le rapport d'expertise du docteur O._ avec ceux des docteurs U._ et D._, les principaux diagnostics posés sont pratiquement superposables. Les conclusions des experts sont divergentes, en revanche, en ce qui concerne les répercussions des atteintes à la santé sur la capacité de travail. Le docteur O._ avait relevé que le recourant se plaignait de céphalées qui s'étaient aggravées, parallèlement à la symptomatologie lombaire et qui étaient accompagnées de nausées et de vomissements. Ce médecin concluait qu'en dépit de ces plaintes, le recourant était en mesure de mettre en valeur une capacité de travail de 70 %. Le docteur U._ a conclu, pour sa part, qu'une capacité résiduelle de travail de 50 % dans une activité adaptée semblait justifiée principalement en raison des céphalées. Le neurologue D._ a quant à lui retenu une capacité résiduelle de travail de 75 % dans une activité adaptée, laquelle devait être réduite à 50 % en raison des crises de migraines.
4.2 Sur la base de ces éléments, il y a lieu de constater que tant le docteur U._ que le docteur D._ ne font pas état d'une modification de l'état de santé du recourant, mais remettent en cause l'appréciation précédente - et fondée sur un même état de fait - du docteur O._. Aussi, en retenant que l'état de santé du recourant sur le plan somatique était demeuré inchangé et qu'il était désormais capable d'exercer une activité légère et adaptée à 70 % après disparition d'une incapacité de travail pour raison psychiatrique, il n'apparaît pas que les premiers juges aient procédé de manière contraire au droit fédéral.
5. Dans la comparaison des revenus, les premiers juges ont fixé le revenu sans invalidité à 57'696 fr. 60 et le revenu d'invalide à 29'777 fr. 45 par année, montants qui ne sont en soi pas contestés par le recourant. En comparant ces chiffres, on obtient un degré d'invalidité de 48,4 %, à savoir un taux ouvrant droit à un quart de rente. Les conditions d'une révision étaient ainsi réunies pour remplacer, à partir du 1er mai 2005, le droit du recourant à une rente entière par un quart de rente (art. 17 LPGA; art. 88bis al. 2 let. a RAI).
6. 6.1 Selon la jurisprudence, les frais d'expertise privée peuvent être inclus dans les dépens mis à la charge de l'assureur social, lorsque cette expertise était nécessaire à la résolution du litige (ATF 115 V 62). Bien que les art. 7 ss du Règlement concernant les frais, dépens et indemnités fixés par le Tribunal administratif fédéral (FITAF; RS 173.320.2) ne prévoient en principe pas de dépens à la charge de la partie qui obtient gain de cause, le juge peut également mettre ces frais d'expertise privée à la charge de l'assureur social dont les conclusions sont finalement admises, lorsque celui-ci a violé son obligation d'instruire la cause d'office (arrêt M. du 21 octobre 2003 [U 282/00] consid. 5.1).
6.2 Tel est le cas en l'espèce. En effet, les premiers juges ont estimé que l'instruction à laquelle avait procédé l'intimé était incomplète, raison pour laquelle ils ont fondé leur appréciation sur les deux expertises versées au dossier par le recourant. Dès lors que lesdites expertises se sont révélées nécessaires à l'instruction de la cause, c'est de manière contraire au droit fédéral que les premiers juges n'ont pas mis les frais afférents à ces dernières à la charge de l'assureur social. Par conséquent, la conclusion du recourant tendant à la prise en charge des frais d'expertises privées par l'intimé doit être admise.
7. Pour ce qui est de la procédure devant le Tribunal fédéral, il se justifie de mettre les frais à la charge du recourant qui n'obtient que très partiellement gain de cause (art. 68 al. 1 LTF). Pour les mêmes raisons, ce dernier ne saurait prétendre à une indemnité de dépens.
Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est partiellement admis. Le chiffre 2 de l'arrêt du Tribunal administrait fédéral du 4 juin 2007 est modifié en ce sens que les frais d'expertises privées du recourant sont mis à la charge de l'intimé pour un montant total de 664 fr. Pour le reste, le recours est rejeté.
2. Les frais judiciaires, arrêtés à 500 fr., sont mis à la charge du recourant.
3. Il n'est pas alloué de dépens pour la procédure fédérale.
4. Le présent arrêt est communiqué aux parties, au Tribunal administratif fédéral, 3ème Cour, et à l'Office fédéral des assurances sociales.
Lucerne, le 28 avril 2008
Au nom de la IIe Cour de droit social
du Tribunal fédéral suisse
p. le Président: La Greffière:
Borella Fretz