Faits: A. X._, ressortissant kosovar né en 1961, a été condamné le 12 septembre 1995 par le Tribunal du district de Y._ (Allemagne) à neuf ans et six mois de réclusion pour trafic de stupéfiants en bande et port d'arme illégal. Le 8 juillet 1999, l'intéressé n'étant pas rentré d'un congé accordé dans le cadre de l'exécution de sa peine, ledit Tribunal a émis un mandat d'arrêt. Le 15 janvier 2001, X._ a été interpellé par la gendarmerie dans le cadre d'un contrôle sur un chantier dans le canton de Vaud. Lors de son audition du même jour, il a allégué avoir quitté son pays d'origine en septembre 1988 pour Fribourg et avoir bénéficié ensuite de trois autorisations de séjour et de travail temporaires d'une durée respective de trois mois et de deux fois quatre mois. Il a ajouté qu'il serait retourné au Kosovo en "décembre 1991" et revenu illégalement en Suisse le 14 janvier 2001. Il a précisé n'avoir "jamais été condamné ni en Suisse ni ailleurs". Sur la base du mandat d'arrêt susmentionné, l'Office fédéral de la justice a émis, le 23 avril 2003, une ordonnance d'arrestation provisoire en vue d'extradition à l'encontre de X._. Le 24 avril 2003, celui-ci a été interpellé par la police à Fribourg et remis le 28 avril 2003 aux autorités allemandes. Par décision du 21 octobre 2003, l'Office fédéral des migrations a prononcé à l'égard de l'intéressé une décision d'interdiction d'entrée en Suisse d'une durée indéterminée en raison de son comportement qui avait donné lieu à des plaintes et parce que son retour en Suisse était indésirable pour des motifs préventifs de police. Lors d'un contrôle de circulation à Fribourg le 7 février 2005, X._ a pris la fuite au volant d'un véhicule et a causé un accident, avant d'être interpellé par la police. Auditionné, il a allégué avoir été relâché de prison en 2004 par les autorités allemandes et renvoyé à Pristina, avant de revenir illégalement en Suisse le 3 février 2005. Le 7 février 2005, le Service de la population et des migrants du canton de Fribourg a rendu une décision de refoulement à l'encontre de X._ et lui a notifié la décision d'interdiction d'entrée en Suisse du 21 octobre 2003 à l'encontre de laquelle l'intéressé a formé un recours. La cause a été rayée du rôle par décision du 6 avril 2005 du Département fédéral de justice et police. Par ordonnance du 21 avril 2005, le juge d'instruction du canton de Fribourg a condamné X._ par défaut à 40 jours d'emprisonnement avec sursis durant deux ans et à une amende de 800 fr. pour opposition aux actes de l'autorité, violation des règles de la circulation, conduite en état d'ébriété, opposition à une prise de sang, violation des devoirs en cas d'accident, vol d'usage et séjour illégal. Le 27 avril 2005, X._ a été interpellé sur un chantier dans le canton de Vaud. Une carte de sortie lui a alors été délivrée avec un délai au 29 avril suivant pour quitter le territoire suisse. L'intéressé s'est marié le 20 décembre 2005 avec une ressortissante suisse auprès de l'état civil de Z._. Le 29 décembre 2005, il a déposé une demande d'autorisation de séjour devant l'Office du séjour et de l'établissement du canton de Neuchâtel. Cet Office a transmis le dossier, en date du 7 février 2006, à l'Office fédéral des migrations en l'informant qu'il était disposé à délivrer une autorisation de séjour à l'intéressé et en le priant de bien vouloir lever la mesure d'interdiction d'entrée en Suisse. Par décision du 27 septembre 2006, l'Office fédéral des migrations a refusé de donner son approbation à l'octroi d'une autorisation de séjour à X._ et a prononcé son renvoi de Suisse. B. Par arrêt du 23 octobre 2008, le Tribunal administratif fédéral a rejeté le recours de X._ en tant qu'il concernait le refus d'approbation d'octroi d'une autorisation de séjour et le renvoi de Suisse. Il a considéré que l'autorité précédente avait refusé à juste titre son approbation à l'octroi d'une autorisation de séjour à l'intéressé. Se référant aux antécédents pénaux de X._, il a estimé, d'une part, que l'intérêt public à l'éloigner l'emportait sur son intérêt privé à rester en Suisse et que, d'autre part, le principe de la proportionnalité était respecté. C'était, en outre, à bon droit que le renvoi de Suisse de l'intéressé avait été prononcé. Le recours a par contre été partiellement admis en tant qu'il avait trait au réexamen de la décision d'interdiction d'entrée en Suisse. En effet, le Tribunal administratif fédéral a jugé qu'une interdiction d'entrée en Suisse de durée indéterminée était contraire au principe de la proportionnalité et il l'a ramenée à une durée limitée au 20 octobre 2013. 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, d'annuler l'arrêt du 23 octobre 2008 du Tribunal administratif fédéral, de lui octroyer une autorisation de séjour, de lever l'interdiction d'entrée en Suisse; subsidiairement, de renvoyer la cause à l'autorité inférieure pour un nouveau jugement dans le sens des considérants et de réduire la durée d'interdiction d'entrée en Suisse lui ayant été imposée. Le recourant se plaint de la violation des art. 7 LSEE et 8 CEDH. Il estime que le Tribunal administratif fédéral a violé le principe de proportionnalité et, en ne tenant pas compte, dans la pesée des intérêts, de certains éléments, a abusé de son pouvoir d'appréciation. L'Office fédéral des migrations conclut au rejet du recours. Le Tribunal administratif fédéral renonce à prendre position, tout en concluant à l'irrecevabilité du recours en tant qu'il porte sur l'interdiction d'entrée en Suisse. D. Par ordonnance du 4 décembre 2008, le Président de la IIe Cour de droit public du Tribunal fédéral a admis la demande d'effet suspensif.