Faits: A. A.X._, ressortissante roumaine née en 1968, est arrivée en Suisse en avril 2002 pour y travailler comme artiste de cabaret. A la suite de son mariage le 28 février 2003 avec B.X._, citoyen suisse, elle a obtenu une autorisation de séjour annuelle dans le canton de Neuchâtel. Le couple s'est séparé en 2005 et le mari a introduit une procédure de divorce sur requête unilatérale en septembre 2008. Parallèlement, A.X._ a été impliquée dans une importante affaire de stupéfiants portant sur la période de mai 2007 à mars 2008. Dans ce cadre, elle a été placée en détention préventive jusqu'en juin 2008. Le 10 juillet de la même année, le Service des migrations du Département de l'économie du canton de Neuchâtel (ci-après: le Service des migrations) a refusé de prolonger l'autorisation de séjour de la prénommée et lui a imparti un délai de départ immédiat pour quitter le territoire cantonal neuchâtelois. B. Dûment représentée par un mandataire professionnel, Me C._, A.X._ a recouru, en date du 10 septembre 2008, contre cette décision. Le 17 septembre 2008, le Service juridique du Département de la justice, de la sécurité et des finances du canton de Neuchâtel (ci-après: le Service juridique), chargé de l'instruction, a requis de l'intéressée le versement d'une avance de frais de 550 fr. Cette décision a été notifiée à l'étude de son mandataire en le rendant attentif aux conséquences d'un défaut de paiement, ainsi qu'à la possibilité de bénéficier de l'assistance administrative. L'avance de frais n'ayant pas été versée, le Service juridique a contacté, en date du 20 novembre 2008, la secrétaire du mandataire afin de s'assurer que la demande d'avance de frais leur était parvenue. Celle-ci leur a confirmé que tel était le cas et que la demande avait été transmise à la recourante. Par décision du 17 décembre 2008, le Conseiller d'Etat, Chef du Département de l'économie du canton de Neuchâtel (ci-après: le Conseiller d'Etat) a déclaré le recours irrecevable pour défaut de paiement de l'avance de frais. Cette décision a été notifiée le même jour au mandataire de A.X._ et elle n'a pas fait l'objet d'un recours. C. Le 27 février 2009, A.X._, agissant par son nouveau mandataire, Me Freddy Rumo, a requis du Conseiller d'Etat la restitution du délai pour s'acquitter de l'avance de frais réclamée le 17 septembre 2008. A l'appui de sa requête, elle expliquait qu'elle avait changé fréquemment de domicile et n'avait, ainsi, eu connaissance de cette décision que le 20 février 2009. Elle alléguait aussi que ses relations avec son précédent mandataire avaient été difficiles et ce de longue date. L'avance de frais de 550 fr. a été versée le 27 février 2009. D. Le 9 mars 2009, le Conseiller d'Etat a rejeté la demande de restitution de délai au motif principal que l'intéressée, se sachant engagée dans une procédure, se devait de prendre les mesures nécessaires pour que les envois postaux lui soient transmis. En outre, n'ayant pas sollicité l'assistance administrative, elle devait s'attendre à recevoir une demande d'avance de frais après le dépôt de son recours du 10 septembre 2008. E. Le 19 juin 2009, la Cour de droit public du Tribunal administratif du canton de Neuchâtel (ci-après: le Tribunal administratif) a rejeté le recours, reprenant en substance les motifs figurant dans la décision du 9 mars 2009 du Conseiller d'Etat. F. Le 21 août 2009, A.X._ a formé un recours en matière de droit public contre l'arrêt du 19 juin 2009 du Tribunal administratif. Elle se plaint de formalisme excessif, ainsi que d'un "abus du pouvoir d'appréciation qui conduit à une violation du droit d'être entendu". Elle allègue que, dûment représentée par un mandataire professionnel, elle était en droit de penser que ce dernier prendrait toutes les dispositions pour la sauvegarde de ses intérêts. N'ayant jamais été mise au courant qu'une avance de frais avait été requise, respectivement du délai pour effectuer le versement et moins encore des conséquences d'un défaut de paiement, elle estime que sa demande de restitution de délai aurait dû être acceptée. Elle conclut, sous suite de frais et dépens, à la recevabilité et à l'admission de son recours, à l'annulation de l'arrêt du Tribunal administratif et au renvoi de la cause à l'autorité inférieure afin qu'elle statue à nouveau. Le Tribunal administratif se réfère aux considérants de l'arrêt attaqué et conclut au rejet du recours. L'Office fédéral des migrations propose également le rejet du recours. Les conclusions du Service juridique ont été déposées hors délai.