Faits: A. Par décision du 7 novembre 2008, la Direction générale des douanes a assujetti à la TVA l'importation d'un tableau par X._. Le 10 décembre 2008, X._ a interjeté recours contre cette décision auprès du Tribunal administratif fédéral. Par décision incidente du 18 décembre 2008, le Tribunal administratif fédéral a imparti à l'intéressé un délai au 26 janvier 2009 pour verser l'avance sur les frais de procédure. Ayant constaté, au vu de l'avis du secteur "Finances et controlling du Tribunal, que l'avance aurait été effectuée le 27 janvier 2009, le juge instructeur en charge du dossier a demandé à X._ d'établir que l'avance de frais avait été versée dans le délai, l'avertissant des conséquences du défaut de production de telles preuves. Par courrier du 6 février 2009, le mandataire de l'intéressé a produit le protocole de paiement et l'avis de débit de sa banque. B. Par arrêt du 19 mars 2009, le juge unique du Tribunal administratif fédéral a déclaré irrecevable le recours du 10 décembre 2008 pour défaut d'avance des frais dans le délai imparti, l'ordre de versement par e-banking ayant bien été donné le 26 janvier 2009 mais son exécution (date d'échéance de l'ordre) n'étant intervenue que le 27 janvier 2009. 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 rendu le 19 mars 2009 par le juge unique du Tribunal administratif fédéral et de renvoyer la cause pour nouvelle décision dans le sens des considérants et entrée en matière sur le recours déposé le 10 décembre 2008, subsidiairement, d'"acheminer le recourant à prouver par toutes voies de droit autorisées les faits exposés dans les présentes écritures" Il se plaint de l'appréciation arbitraire des preuves, de la violation des art. 21 al. 3 et 63 al. 4 PA et de l'interdiction du formalisme excessif. La Direction générale des douanes s'en remet à justice. Le Tribunal administratif fédéral renonce à déposer des observations. D. Par ordonnance du 26 mai 2009, le Président de la IIe Cour de droit public a admis la requête d'effet suspensif déposée par l'intéressé.