Faits:
A. X._, ressortissant français né en 1947, réside en Suisse depuis le 25 janvier 1996. Il était d'abord au bénéfice d'une autorisation de séjour imputée sur le contingent cantonal, puis d'une autorisation CE/AELE.
Le recourant a fait l'objet des condamnations pénales suivantes:
- le 29 avril 1996, le Tribunal correctionnel d'Albertville a prononcé une peine de six mois d'emprisonnement à son égard pour faux et usage de faux en écriture privée de commerce ou de banque, et faux dans l'écriture publique,
- le 30 juin 1998, le Tribunal correctionnel du district de Lausanne (ci-après: le Tribunal correctionnel) l'a condamné pour escroquerie, abus de confiance, insoumission à une décision de l'autorité et délit contre la loi fédérale sur le matériel de guerre, à six mois d'emprisonnement et à trois ans d'expulsion avec sursis pendant trois ans,
- le 25 juillet 2000, il a été condamné par le Tribunal correctionnel du district d'Echallens pour abus de confiance et escroquerie à quatre mois d'emprisonnement avec sursis et délai d'épreuve de quatre ans, peine partiellement complémentaire au jugement du 30 juin 1998,
- le 7 mars 2006, le Tribunal correctionnel l'a condamné par défaut pour abus de confiance, escroquerie et recel à quinze mois d'emprisonnement, peine partiellement complémentaire à celle prononcée le 25 juillet 2000; ledit Tribunal a également révoqué le sursis à l'expulsion qui lui avait été accordé par jugement du 30 juin 1998 par le Tribunal correctionnel, ordonné son expulsion du territoire suisse pour une durée de trois ans, révoqué le sursis qui lui avait été accordé le 25 juillet 2000 par le Tribunal correctionnel d'Echallens et ordonné l'exécution de la peine de quatre mois d'emprisonnement. Le Tribunal correctionnel a confirmé son jugement du 7 mars 2006 par arrêt du 26 juillet 2006, le recourant persistant à faire défaut.
- le 19 juin 2008, X._ a été condamné par le Tribunal correctionnel pour abus de confiance, escroquerie et faux dans les titres à une peine privative de liberté de douze mois avec sursis pendant cinq ans, peine partiellement complémentaire à celle prononcée par le Tribunal correctionnel le 26 juillet 2006.
Le Service de la population du canton de Vaud (ci-après: le Service de la population), par décision du 5 février 2007, a révoqué l'autorisation de séjour CE/AELE de X._ et lui a imparti un délai d'un mois pour quitter la Suisse. Il justifiait cette décision par la gravité des peines prononcées à l'égard de l'intéressé dans les jugements de 1998, 2000 et 2006.
B. Le 17 décembre 2008, l'Office fédéral des migrations a rendu, à l'encontre de X._, une décision d'interdiction d'entrée en Suisse valable jusqu'au 16 décembre 2013, motivée comme suit:
"Atteinte et mise en danger de la sécurité et l'ordre publics en raison de son comportement (abus de confiance, escroquerie et faux dans les titres). Art. 67 al. 1 let. a LEtr."
Par décision incidente du 19 juin 2009, le Tribunal administratif fédéral a rejeté la demande de X._ tendant à la restitution de l'effet suspensif du recours. Puis, le 16 mars 2010, il a rejeté le recours sur le fond.
C. Agissant par la voie du recours en matière de droit public, X._ demande au Tribunal fédéral, sous suite de frais et dépens, de réformer l'arrêt du 16 mars 2010 du Tribunal administratif fédéral en ce sens que la décision d'interdiction d'entrée en Suisse du 17 décembre 2008 prononcée par l'Office fédéral des migrations est nulle. Subsidiairement, il requiert le renvoi de la cause à l'autorité précédente pour nouveau jugement dans le sens des considérants. Il dénonce une appréciation arbitraire des preuves, une violation de l'art. 29 Cst. et du droit conventionnel.
Le Service de la population et le Tribunal administratif fédéral ont renoncé à se déterminer sur le recours. L'Office fédéral des migrations a conclu au rejet du recours dans la mesure de sa recevabilité.

Considérant en droit:
1. 1.1 Dirigé contre un arrêt final (<ref-law>), rendu dans une cause de droit public (<ref-law>) par le Tribunal administratif fédéral (<ref-law>), le recours a été déposé, par le destinataire de l'arrêt attaqué qui a un intérêt digne de protection à l'annulation ou à la modification de celui-ci (<ref-law>), dans le délai prévu par la loi (<ref-law>) et les formes prescrites (<ref-law>).
En outre, le présent recours ne tombe pas sous le coup de l'art. 83 let. c ch. 1 LTF qui exclut le recours en matière de droit public contre les décisions en matière de droit des étrangers qui concernent l'entrée en Suisse. En effet, afin de respecter le droit conventionnel, cette voie de droit reste ouverte aux ressortissants communautaires en vertu de l'art. 11 par. 1 et 3 de l'Accord du 21 juin 1999 entre la Confédération suisse d'une part, et la Communauté européenne et ses Etats membres, d'autre part, sur la libre circulation des personnes (ci-après: ALCP ou l'Accord; RS 0.142.112.681) qui prévoit une double instance de recours (cf. 2C_664/2009 consid. 1; 2C_375/2007 consid. 2; sous l'OJ: <ref-ruling> consid. 1 p. 353 ss). En sa qualité de ressortissant français, le recourant bénéficie de cette exception.
1.2 Selon l'<ref-law>, le recours peut critiquer les constatations de fait à la double condition que les faits aient été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> et que la correction du vice soit susceptible d'influer sur le sort de la cause, ce que le recourant doit rendre vraisemblable par une argumentation répondant aux exigences des art. 42 al. 2 et 106 al. 2 LTF (cf. <ref-ruling> consid. 1.4.3 p. 254/255). La notion de "manifestement inexacte" figurant à l'<ref-law> correspond à celle d'arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 1.5 p. 401; <ref-ruling> consid. 1.2.2 p. 252, 384 consid. 4.2.2 p. 391). Pour qu'il y ait constatation manifestement inexacte, il faut que l'autorité n'ait pas pris en compte, sans raison sérieuse, un élément de preuve propre à modifier la décision, qu'elle se soit trompée manifestement sur le sens et la portée d'un moyen de preuve ou encore qu'en se fondant sur les éléments recueillis, elle en tire des déductions insoutenables (<ref-ruling> consid. 2.1 p. 9).
2. 2.1 Le recourant fait tout d'abord valoir une violation de son droit d'être entendu garanti par l'art. 29 Cst. Il rappelle que la notification de la décision d'interdiction d'entrée du 17 décembre 2008 de l'Office fédéral des migrations a été tentée sans succès à son ancienne adresse en France et est revenue à l'Office fédéral des migrations avec la mention "n'habite pas à l'adresse mentionnée". Le fait qu'il ait eu connaissance ultérieurement de l'existence et du contenu de cette décision, de manière à pouvoir saisir le Tribunal administratif fédéral, n'aurait eu aucun effet guérisseur. Dès lors, la décision d'interdiction d'entrée devrait être considérée comme nulle au vu du défaut de notification. Il invoque, à l'appui de ce grief, l'<ref-ruling>.
2.2 Dans cet arrêt, le destinataire de la décision administrative en cause n'en avait pas eu connaissance. Dès lors, cette décision ne lui était pas opposable. La situation qui prévaut dans le cas présent est très différente puisque la décision d'interdiction d'entrée du 17 décembre 2008 est parvenue au recourant qui, conformément aux règles de la bonne foi, a alors entrepris toutes les démarches utiles pour sauvegarder ses droits. Dans une telle situation, le Tribunal fédéral estime que, si la notification irrégulière d'une décision n'entraîne aucun préjudice pour les parties, l'existence de vices de notification n'entraîne pas forcément sa nullité (<ref-ruling> consid. 3 p. 98 ss). Ainsi, la protection des parties est suffisamment réalisée lorsque la notification irrégulière atteint son but malgré cette irrégularité (<ref-ruling> consid. 6 p. 253).
Il y a donc lieu d'examiner, d'après les circonstances du cas concret, si la partie a réellement été induite en erreur par l'irrégularité de la notification et a, de ce fait, subi un préjudice. Il s'agit, en effet, de s'en tenir aux règles de la bonne foi, qui imposent une limite à l'invocation d'un vice de forme (<ref-ruling> consid. 3a/aa p. 99). Lorsque la connaissance d'une décision est retardée à cause d'une notification irrégulière, on considère que la notification a eu lieu au moment où la décision est effectivement parvenue au destinataire, sans qu'il faille la réitérer. Tel est précisément ce qui s'est produit en l'espèce. En effet, la décision d'interdiction d'entrée n'a pas pu être notifiée au recourant à son ancienne adresse en France mais l'acte lui est malgré tout parvenu ultérieurement. Il a alors pu faire valoir ses droits en justice et n'a subi aucun préjudice de l'échec de la notification initiale. Le grief de nullité de la décision d'interdiction d'entrée du 17 décembre 2008 pour défaut de notification doit donc être rejeté.
3. 3.1 Le recourant se plaint ensuite de ce que le Tribunal administratif fédéral s'est prononcé sur l'art. 5 Annexe I à l'ALCP comme première autorité, l'Office fédéral des migrations n'ayant abordé l'interdiction d'entrer en Suisse qu'au regard de la loi fédérale sur les étrangers du 16 décembre 2005 (RS 142.20). Il aurait ainsi été privé de la double instance de recours garantie par l'<ref-law>.
3.2 L'<ref-ruling>, dont se prévaut le recourant, a, en effet, ouvert aux ressortissants communautaires le recours devant le Tribunal fédéral contre les décisions en matière de droit des étrangers qui concernent l'entrée en Suisse, afin de leur garantir la double instance de recours prévue par l'<ref-law> (cf. consid. 1.1). Or, dans la présente affaire, le recourant a précisément disposé d'une double instance de recours puisqu'il a tout d'abord saisi le Tribunal administratif fédéral, puis le Tribunal fédéral. Il a pu, devant ces deux instances judiciaires, faire valoir la violation de l'Accord (cf. art. 2 al. 4 et 49 PA par renvoi de l'art. 37 de la loi fédérale du 17 juin 2005 sur le Tribunal administratif fédéral [LTAF; RS 173.32] et <ref-law>). Or, la violation du droit inclut le cas où un texte de loi aurait dû être appliqué et où il ne l'a pas été. Ainsi, le fait que l'Office fédéral des migrations n'a pas fondé sa décision sur l'ALCP n'est pas contraire à l'<ref-law>, dès lors que le recourant a pu faire valoir la violation de l'Accord devant le Tribunal administratif fédéral puis devant le Tribunal fédéral. En outre, c'est à bon droit que le Tribunal administratif fédéral a examiné la décision d'interdiction d'entrée en Suisse au regard de l'ALCP. L'effet dévolutif du recours (cf. <ref-law>) l'y autorisait et le principe jura novit curia l'y contraignait.
Le recourant a ainsi bénéficié de la double instance de recours prévue à l'<ref-law> et son grief doit donc être rejeté.
4. Enfin, le recourant conteste l'existence d'un risque de récidive, estimant que le Tribunal administratif fédéral a fait preuve d'arbitraire dans l'appréciation des preuves du cas d'espèce.
Tel que formulé, le grief est irrecevable puisque l'argumentation est purement appellatoire (consid. 1.2 ci-dessus). Au demeurant, le Tribunal administratif fédéral a soigneusement examiné cette question et il suffit de renvoyer à l'arrêt entrepris (<ref-law>).
5. Au vu de ce qui précède, le recours doit être rejeté dans la mesure où il est recevable. Succombant, le recourant doit supporter les frais judiciaires (art. 65 et 66 al. 1 LTF). Il n'est pas alloué de dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. Les frais judiciaires, arrêtés à 2'000.-- fr, sont mis à la charge du recourant.
3. Le présent arrêt est communiqué au mandataire du recourant, au Tribunal administratif fédéral et à l'Office fédéral des migrations, ainsi qu'au Service de la population du canton de Vaud.
Lausanne, le 4 octobre 2010
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
Zünd Kurtoglu-Jolidon