Faits: A. Dans le cadre de procédures pénales ouvertes dans les cantons de Vaud, Jura et Neuchâtel, les magistrats en charge de l'instruction ont fait parvenir au Service des tâches spéciales du Département fédéral de l'environnement, des transports, de l'énergie et de la communication (depuis le 1er janvier 2008: le Service de surveillance de la correspondance par poste et télécommunication; ci-après: le Service de surveillance ou le Service), entre 2002 et 2004, cinq ordonnances requérant la production des communications téléphoniques effectuées, durant diverses périodes, sur les lieux où des infractions avaient été commises. Un juge d'instruction du canton de Vaud, le seul canton à recourir devant le Tribunal de céans, a notamment rendu une ordonnance le 12 novembre 2004. Cette dernière, relative à une enquête pour cambriolage, demandait "tous les numéros de portables ayant reçus ou émis des appels durant les deux périodes précitées (le 3 septembre 2004 de 4h00 à 5h30 et le 28 octobre 2004 de 3h00 à 4h30) par les antennes couvrant le secteur de la bijouterie Kaenel, à Villars-sur-Ollon, avenue centrale, coordonnées géographiques 570.417/127.480". Après que les autorités cantonales compétentes eurent autorisé les mesures nécessaires, soit des recherches par champ d'antennes, le Service de surveillance a ordonné à Swisscom Mobile SA (ci-après: Swisscom), Orange Communications SA (ci-après: Orange) et Sunrise Communications SA (ci-après: Sunrise) (ci-après: les fournisseurs ou les opérateurs) de produire les informations demandées. Le principe des recherches par champ d'antennes faisant l'objet d'un recours au Tribunal fédéral par certains fournisseurs (ATF 130 II 249), le Service de surveillance a suspendu la procédure en attendant la décision du Tribunal de céans. Les recours ayant été rejetés par arrêts du 13 avril 2004 et les informations requises obtenues des fournisseurs, ledit Service les a fait parvenir, en juin 2004, aux juges d'instruction les ayant requises. B. Afin de faciliter la facturation des recherches par champ d'antennes, le Service de surveillance a décidé de fixer un tarif forfaitaire applicable aux demandes de recherches. Dans cette perspective, le Service ne possédant pas les personnes ayant les connaissances nécessaires dans ce domaine, il a fait appel aux fournisseurs. Ainsi, le 20 octobre 2004, il a requis de leur part des explications relatives à leur façon de procéder lors d'une telle recherche et aux coûts engendrés. Par message électronique du 4 novembre 2004, Swisscom, qui a fondé son calcul des frais sur une évaluation de 8 à 10 cellules, a expliqué que, dans le cadre d'une telle recherche, il fallait procéder à une "analyse de réseau" laquelle permettait de découvrir par quelles cellules avait eu lieu une communication téléphonique à l'endroit de l'infraction pendant la période déterminée. Elle comptait pour cela une heure et demie de travail au tarif horaire de 300 fr. L'analyse des données par cellule identifiée ("analyse de cellule" qui permet d'obtenir les numéros de téléphone qui ont communiqué par ces cellules) prenait ensuite approximativement une heure, également au tarif de 300 fr. Puis, l'activité consistant à rendre lisibles les données à l'état brut issues du système informatique nécessitait une demi-heure à 300 fr. Swisscom a ajouté à cela le coût d'exploitation et d'acquisition du know-how pour un montant de 250 fr. Ainsi, au total, le coût par cellule analysée se montait à 1'150 fr. Dans un courrier du 5 novembre 2004, Orange a basé son calcul des frais sur une évaluation de cinq cellules. Deux heures de travail étaient nécessaires afin de déterminer si une cellule pouvait entrer en considération dans un cas particulier, pour un coût de 1'600 fr. L'analyse subséquente de chaque cellule requérait environ cinq à six heures. Orange comptait, pour cette activité, 4'500 fr. pour cinq cellules. Enfin, il fallait deux heures à l'"Operational Team" pour rendre les données lisibles pour un montant de 200 fr. Au total, les frais s'élevaient à 6'300 fr. pour cinq cellules, soit 1'260 fr. par cellule. L'évaluation des coûts établie par Sunrise le 5 novembre 2004 se fondait également sur cinq cellules. Cette société a retenu une heure de travail à 300 fr. pour l'activité liée à la réception de la requête (discussion avec le Service de surveillance, recherche des coordonnées lorsque seule une adresse est communiquée). Pour évaluer si cinq cellules pouvaient entrer en considération dans un cas particulier, huit heures étaient nécessaires au tarif horaire de 375 fr. Puis, l'analyse des différentes cellules était effectuée par le département "Police liaison", qui utilisait un système spécialement développé pour rechercher les communications dans les diverses bases de données existantes. Ce travail nécessitait un quart d'heure par cellule, au tarif horaire de 300 fr. A cela s'ajoutait un quart d'heure supplémentaire pour rendre les données lisibles, au même tarif horaire. En outre, pour cinq cellules, il fallait trois quarts d'heure afin de transférer les données sur disquette ou CD et préparer l'envoi, toujours au même tarif. Un montant de 20 fr. était prévu pour l'envoi. Le coût total, pour cinq cellules, était de 4'295 fr., soit 859 fr. par cellule. Le 2 décembre 2004, a eu lieu une réunion organisée par le Service de surveillance. Selon le procès-verbal du 15 décembre 2004, y participaient des représentants de Bluewin, d'Orange, de Sunrise et de Swisscom, un représentant du ministère public et un de la police du canton de Zurich, ainsi que deux experts de la société AWK Engineering AG. Cette séance devait permettre au Service de surveillance de comprendre la façon de procéder des opérateurs lors d'une recherche par champ d'antennes et d'estimer le temps nécessaire pour ce faire, afin de déterminer un tarif forfaitaire applicable à de telles recherches. Par lettre du 20 décembre 2004, le Service de surveillance a communiqué aux opérateurs le tarif arrêté pour leurs prestations. Il a distingué deux phases dans la recherche par champ d'antennes, soit l'analyse de réseau et l'analyse de cellules. Il a fixé la première à 2'200 fr., dont 2'000 fr. payables aux opérateurs et 200 fr. pour ledit Service, et la seconde à 600 fr., somme reversée dans son intégralité aux fournisseurs. C. Les 30 novembre et 7 décembre 2005, le Service de surveillance a rendu cinq décisions portant sur les émoluments et indemnités relatifs aux cinq recherches par champ d'antennes susmentionnées requises par les magistrats des différents cantons. Les montants étaient fixés conformément au tarif prévu dans la lettre du 20 décembre 2004. Les cantons du Jura et de Neuchâtel devaient s'acquitter respectivement d'un montant total de 15'000 fr. et de 13'200 fr., chacun pour une requête. Le canton de Vaud a reçu trois factures d'un montant respectif de 30'600 fr., 8'600 fr. et 24'600 fr. pour trois demandes différentes, dont celle du 12 novembre 2004 qui fait l'objet de la présente procédure. Celle-ci se compose des montants suivants: 5'800 fr. pour Sunrise (analyse de réseau et de six cellules), 10'600 fr. pour Swisscom (analyse de réseau et de quatorze cellules) et 8'200 fr. pour Orange (analyse de réseau et de dix cellules). D. Les cantons de Vaud, du Jura et de Neuchâtel ont recouru à l'encontre des décisions des 30 novembre et 7 décembre 2005 du Service de surveillance auprès de la Commission fédérale de recours en matière d'infrastructures et d'environnement qui a été, par la suite, dissoute, l'affaire étant reprise par le Tribunal administratif fédéral. Ne pouvant décider du caractère équitable des indemnités dues pour une recherche par champs d'antennes sans l'aide des trois opérateurs, ledit Service a demandé l'intervention de ceux-ci en qualité de parties, ce qui a été admis. Après instruction de la cause, notamment de questions posées par écrit au Service de surveillance, le Tribunal administratif fédéral a, par arrêt du 17 février 2009, rejeté les recours. Il a jugé que le forfait retenu pour une recherche par champ d'antennes par le Service de surveillance n'était pas disproportionné. Il en allait de même des opérations effectuées dans le cadre des demandes en cause ayant abouti aux factures contestées. E. Agissant par la voie du recours en matière de droit public, le canton de Vaud demande au Tribunal fédéral, sous suite de frais, de réformer la décision du 7 décembre 2005 du Service de surveillance en ce sens que l'émolument dû est fixé à un montant largement inférieur à 24'600 fr., d'annuler l'arrêt du 17 février 2009 du Tribunal administratif fédéral et de lui renvoyer la cause pour une nouvelle décision. Il invoque une violation de son droit d'être entendu, du droit fédéral de fond applicable à la cause, ainsi que des principes de proportionnalité et de l'interdiction de l'arbitraire. Le Service de surveillance conclut au rejet du recours. Orange, Swisscom et Sunrise demandent également, sous suite de frais et dépens, le rejet du recours. Le Tribunal administratif fédéral renonce à déposer des observations. Le Département fédéral de justice et police conclut à l'irrecevabilité du recours et, s'il devait être déclaré recevable, à son rejet. Par ordonnance du 27 mai 2009, le Président de la IIe Cour de droit public a rejeté la demande d'effet suspensif. 