Faits:
A. Le 20 octobre 2010, X._ a déposé une demande en paiement contre Y._ SA devant le Tribunal d'arrondissement de Lausanne. Il a notamment conclu au paiement d'une indemnité pour licenciement abusif au sens de l'<ref-law>.
Le 27 octobre 2010, le Tribunal d'arrondissement a requis une avance de frais de 500 fr. à payer d'ici au 16 novembre 2010, précisant que "l'office ne procéderait à aucune opération avant que le paiement ait été effectué", référence étant faite aux art. 90 du Code de procédure civile vaudois du 14 décembre 1996 (CPC/VD) et 13 de l'ancien Tarif des frais judiciaires en matière civile du 4 décembre 1984 (aTFJC).
Le demandeur a admis avoir omis de payer l'avance de frais dans le délai imparti.
Par courrier du 29 décembre 2010, le Tribunal d'arrondissement a constaté que l'émolument de demande n'avait pas été avancé dans le délai fixé et qu'en l'état, le demandeur était déchu de son droit à la notification de cette écriture. Il précisait que, sous réserve de restitution par voie de réforme qui devrait être requise d'ici le 20 janvier 2011, il constaterait cette déchéance et ordonnerait que la cause soit rayée du rôle.
L'avance de frais a été réglée par le demandeur le 13 janvier 2011. Il n'a toutefois déposé aucune requête de réforme dans le délai fixé au 20 janvier 2011.
B. Par décision du 15 février 2011, le Président du Tribunal d'arrondissement de Lausanne a rayé du rôle sans frais la cause dirigée contre Y._ SA.
Par arrêt du 19 mai 2011, la Cour d'appel civile du Tribunal cantonal vaudois a rejeté l'appel et confirmé le jugement de première instance.
C. X._ exerce un recours en matière civile au Tribunal fédéral contre l'arrêt cantonal du 19 mai 2011. Il conclut à son annulation, à ce qu'il soit constaté que l'avance de frais a été faite valablement et au renvoi de la cause à la Cour civile pour statuer sur les dépens, puis au Tribunal d'arrondissement pour que la procédure soit ouverte et suive son cours. En substance, le recourant fait grief à la cour précédente d'avoir violé les principes de la bonne foi et de la proportionnalité, ainsi que les interdictions de formalisme excessif et d'arbitraire.
L'intimée se borne à souligner que le recourant n'expose pas en quoi l'application par les tribunaux vaudois des règles de procédure cantonales serait contraire à la Constitution fédérale.

Considérant en droit:
1. 1.1 L'arrêt attaqué, qui confirme que la demande est caduque et qu'elle doit être rayée du rôle, met fin à la procédure; il s'agit d'une décision finale (<ref-law>). Celle-ci a été rendue en matière civile (<ref-law>) par une autorité cantonale de dernière instance (<ref-law>).
Interjeté par la partie qui a succombé dans ses conclusions en paiement (<ref-law>) dans une affaire pécuniaire en matière de droit du travail dont la valeur litigieuse atteint le seuil de 15'000 fr. (<ref-law>), le recours est en principe recevable puisqu'il a été déposé dans le délai (art. 46 al. 1 let. b, 48 al. 1 et 100 LTF) et la forme (<ref-law>) prévus par la loi.
1.2 Le recours en matière civile peut être interjeté pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. En conséquence, il peut être formé pour violation d'un droit constitutionnel (<ref-ruling> consid. 2.1 p. 247; <ref-ruling> consid. 2.4 p. 313).
La procédure litigieuse a été ouverte avant le 1er janvier 2011, de sorte qu'elle restait soumise à l'ancien droit de procédure jusqu'à la clôture de l'instance par l'arrêt cantonal (<ref-law>). Le recours en matière civile au Tribunal fédéral n'est toutefois pas ouvert pour se plaindre d'une violation du droit cantonal, hormis certaines exceptions qui n'entrent pas en considération ici (art. 95 et 96 LTF). La recourante ne peut donc se plaindre que de la violation d'un droit constitutionnel en relation avec l'application du droit cantonal (<ref-ruling> consid. 4.3 p. 521 s., 578 consid. 6.1 p. 580).
Par exception à la règle selon laquelle il applique le droit d'office (<ref-law>), le Tribunal fédéral ne peut entrer en matière sur la violation d'un droit constitutionnel ou sur une question relevant du droit cantonal ou intercantonal que si le grief a été invoqué et motivé de manière précise par la partie recourante (<ref-law>).
1.3 Le Tribunal fédéral conduit son raisonnement juridique sur la base des faits établis par l'autorité précédente (<ref-law>). Il ne peut s'en écarter que si les faits ont été établis de façon manifestement inexacte - ce qui correspond à la notion d'arbitraire (ATF <ref-ruling> consid. 2.4 p. 314; <ref-ruling> consid. 1.5 p. 130, 397 consid. 1.5 p. 401) - ou en violation du droit au sens de l'<ref-law> (<ref-law>). Il incombe à la partie recourante, qui entend s'écarter des constatations de l'autorité précédente, d'expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'<ref-law> seraient réalisées, faute de quoi il n'est pas possible de tenir compte d'un état de fait qui diverge de celui contenu dans la décision attaquée (<ref-ruling> consid. 1.4 p. 287 s. et consid. 6.2 p. 288). Une rectification de l'état de fait ne peut être demandée que si elle est de nature à influer sur le sort de la cause (<ref-law>).
1.4 Le Tribunal fédéral ne peut aller au-delà des conclusions des parties (<ref-law>). Toute conclusion nouvelle est irrecevable (<ref-law>).
2. 2.1 Le recourant reproche à la cour cantonale d'avoir violé les principes de la bonne foi et de la proportionnalité, ainsi que les interdictions de formalisme excessif et d'arbitraire.
Il développe son argumentation essentiellement sous l'angle du formalisme excessif (art. 29 al. 2 Cst.), arguant que l'institution de la réforme, telle qu'elle est consacrée par les <ref-law>/VD, n'est justifiée en l'espèce par aucun intérêt digne de protection (pour l'examen du grief, cf. infra consid. 2.2 et 2.4).
Si la motivation du moyen tiré du principe de la bonne foi (art. 9 Cst.) peut être considérée comme suffisante pour que la Cour de céans entre en matière (cf. infra consid. 2.3), il n'en va pas de même de celle fournie en lien avec le grief de l'arbitraire (art. 9 Cst.); en effet, à lire l'argumentation du recourant, on peine à discerner en quoi les dispositions cantonales invoquées auraient été appliquées arbitrairement et le moyen se révèle donc irrecevable (cf. encore infra consid. 2.4 et 2.5). Quant à la transgression du principe de la proportionnalité, ce moyen est invoqué mais pas motivé; il n'est pas recevable (cf. supra consid. 1.2).
2.2 Il n'y a pas de formalisme excessif prohibé par l'art. 29 al. 2 Cst. ni d'arbitraire ou de comportement contraire aux règles de la bonne foi au sens de l'art. 9 Cst. de la part de l'autorité à ne pas entrer en matière sur une demande dont la recevabilité est subordonnée au versement d'une avance de frais dans un délai déterminé selon le droit de procédure applicable, pour autant que son auteur ait été averti de façon appropriée du montant à verser, du délai imparti pour le paiement et des conséquences de l'inobservation de ce délai (<ref-ruling> consid. 3.3 p. 405; <ref-ruling> consid. 5 p. 111; <ref-ruling> consid. 4 p. 523). Tel est le cas en l'espèce. On peut laisser indécise la question de savoir si le simple renvoi aux <ref-law>/VD et 13 aTFJC rendait la partie suffisamment attentive aux conséquences de l'inobservation du délai. En effet, celles-ci ont été exposées sans aucune ambiguïté dans le courrier du 29 décembre 2010 envoyé par l'autorité de première instance; cette dernière, constatant que l'émolument requis n'avait pas été avancé, a informé le demandeur qu'il était déchu du droit à la notification de son écriture et que, sous réserve d'une restitution par voie de réforme devant être requise par le demandeur jusqu'au 20 janvier 2011, le tribunal constaterait cette déchéance et ordonnerait que la cause soit rayée du rôle.
2.3 En l'espèce, il suffit de lire le courrier du 29 décembre 2010 du Tribunal d'arrondissement pour comprendre qu'un deuxième délai (avec une échéance au 20 janvier 2011) a été accordé au recourant pour lui permettre de poursuivre la procédure, l'avance de frais n'ayant pas été effectuée dans le premier délai fixé au 16 novembre 2011.
Le recourant estime toutefois avoir été trompé par la formulation employée dans cette lettre. Invoquant le principe de la bonne foi (art. 9 Cst.), il prétend que les termes utilisés sont "inaccessibles au commun des mortels" et que, comme "tout citoyen lambda", il pouvait légitimement penser, en tant que mandataire de tradition genevoise, qu'il suffisait simplement de payer l'avance de frais requise avant l'échéance du 20 janvier 2011.
Le courrier du 29 décembre 2010 mentionne clairement que, si le demandeur entend éviter que la cause soit rayée du rôle, il doit demander la restitution du délai par voie de réforme. En l'espèce, le recourant était représenté par un avocat et il ne s'agit pas de savoir ce que pouvait comprendre un "citoyen lambda". L'autorité judiciaire a expressément indiqué à l'avocat une procédure à suivre (la réforme) pour obtenir la restitution du délai fixé initialement pour faire l'avance de frais, et elle n'a pas fait mention d'un délai supplémentaire qui aurait été prévu simplement pour payer cette avance. On ne saurait ainsi dire que l'autorité cantonale, par son attitude (en l'occurrence l'envoi du courrier litigieux), a fait croire qu'il était suffisant de verser l'avance de frais jusqu'au 20 janvier 2011 ou qu'elle aurait donné des informations erronées sur la procédure à suivre d'une façon propre à inciter le demandeur à ne pas faire valoir ses moyens de manière utile (cf. <ref-ruling> consid. 4a p. 270 et les arrêts cités; arrêt 4C.82/2006 du 27 juin 2006 consid. 4.1 publié in PJA 2007 p. 217; JEAN-FRANÇOIS EGLI, La protection de la bonne foi dans le procès, in Juridiction constitutionnelle et Juridiction administrative, Zurich, p. 237 et les références). Si l'avocat avait un doute quant à la procédure évoquée par l'autorité, il devait s'en inquiéter et se renseigner. Il est à cet égard sans importance que le mandataire ne soit pas établi dans le canton de Vaud; il a entendu y pratiquer et devait donc se soumettre aux règles procédurales alors en vigueur dans ce canton.
Le moyen est infondé.
Quant à l'<ref-law>, il n'était pas encore applicable et c'est en vain que le recourant soutient que le tribunal de première instance aurait dû l'interpeller pour lui indiquer que le versement n'était pas suffisant pour sauvegarder ses droits.
2.4 Le recourant estime que l'exigence de la réforme procède d'un formalisme excessif, cette procédure empêchant ou compliquant de manière insoutenable l'application du droit. Il souligne qu'il n'y a aucun intérêt digne de protection de faire dépendre le paiement de l'avance de frais dans le "délai de grâce" d'une simple lettre indiquant formellement que le recourant se réforme. Selon lui, le versement de l'avance de frais opéré le 13 janvier 2011 doit être considéré comme une requête de réforme par actes concluants.
Contrairement à ce que pense le recourant, l'institution de la réforme n'est pas dépourvue de sens et de but. Pour bien comprendre cette institution, il faut observer que la même partie ne peut se réformer que deux fois (au plus) dans la même instance (<ref-law>/VD). Cette limitation est édictée dans l'intérêt général, afin d'éviter un allongement des procès (cf. arrêt de la Chambre des recours du Tribunal cantonal vaudois du 23 septembre 1986 consid. 4a publié in JdT 1987 III 45). Elle garde tout son sens en présence d'un demandeur qui a d'emblée été négligent après avoir transmis sa demande à l'autorité, omettant de faire l'avance de frais dans le délai prescrit. Si, comme c'est le cas en l'espèce, il ne remplit pas les conditions de l'<ref-law>/VD, ce plaideur doit rattraper son erreur en utilisant un de ses deux droits à la réforme dans le cours de la même procédure. N'ayant alors plus qu'une unique possibilité de se réformer, le plaideur négligent sera incité à s'organiser de façon plus efficace à l'avenir, de manière à respecter les délais fixés ultérieurement en cours d'instance (cf. arrêt 4P.47/2006 du 2 juin 2006 consid. 4), ce qui contribue globalement à la célérité du procès.
S'agissant de la forme sous laquelle la requête de réforme doit être présentée, on ne saurait admettre que celle-ci puisse être requise "par actes concluants", du fait que le paiement de l'avance a été effectué dans le délai fixé par l'autorité judiciaire. En effet, l'<ref-law>/VD prévoit notamment que la partie qui désire obtenir la restitution d'un délai doit demander l'autorisation de se réformer; selon l'<ref-law>/VD, la requête de réforme doit énoncer les motifs qui la fonde. Il s'agit donc pour le requérant de reconnaître (par l'indication des motifs) qu'il n'a pas respecté une règle et de manifester clairement sa volonté de se réformer (en demandant l'autorisation à l'autorité). Une requête expresse adressée à l'autorité est dès lors indispensable. Elle est également dans l'intérêt du requérant, puisqu'elle permet de garantir qu'il est parfaitement conscient qu'il utilise un de ses deux droits à la réforme. Quant à la forme écrite qui a été exigée, le recourant observe lui-même que la requête de réforme se résume à "une simple lettre de deux lignes" et l'on ne saurait ainsi parler de formalisme excessif en l'espèce.
Le grief doit être déclaré mal fondé.
Cela étant, on ne voit pas que la cour précédente ait appliqué les art. 153 et 154 CPC/VD de manière arbitraire en refusant d'admettre qu'une requête de réforme puisse découler, implicitement, du paiement de l'avance de frais. Fût-il recevable, ce grief serait ainsi de toute façon mal fondé.
2.5 Le recourant revient à la charge en considérant que l'<ref-law>/VD a été manifestement mal appliqué. Il soutient que, faute de validation de la demande par le paiement, la cause n'était pas ouverte et qu'en l'absence d'une procédure principale ouverte, il ne pouvait y avoir de procédure incidente et donc de réforme possible.
Il appartenait au recourant d'invoquer l'arbitraire (art. 9 Cst.) et de démontrer, par une motivation circonstanciée, que la cour cantonale a appliqué de façon insoutenable la règle cantonale considérée. La critique ne remplit en l'espèce pas ces exigences et elle doit être déclarée irrecevable.
Quoiqu'il en soit, l'argumentation repose sur une prémisse erronée. En effet, la "procédure principale" était à l'évidence ouverte puisque la demande a été déposée (cf. <ref-law>/VD). Le moyen invoqué, pour autant qu'on le comprenne bien, est dès lors sans consistance.
2.6 Quant au reproche selon lequel la décision cantonale priverait le recourant de son droit d'action, puisque le délai de l'<ref-law> était échu au moment du paiement de l'avance de frais, il tombe à faux.
La cour précédente s'est limitée à confirmer que le recourant, qui n'a pas fait l'avance de frais dans le délai fixé par la procédure cantonale, était déchu de son droit de requérir toute opération ultérieure (notamment l'envoi de la demande à la partie adverse) (cf. <ref-law>/VD; arrêt de la Chambre des recours du Tribunal cantonal vaudois du 12 mars 2003 consid. 2 publié in JdT 2005 III 116) et que cette déchéance entraînait la caducité de la demande. Celle-ci a été examinée uniquement dans une perspective procédurale par la cour cantonale qui n'a donc pas exclu, sous cet angle, que le demandeur puisse faire valoir sa prétention en justice pour une nouvelle action (cf. ATF <ref-ruling> consid. 5 p. 111 s.).
Dans sa critique, le recourant tire argument d'une prétendue perte du droit au fond. Tel n'est pas l'objet du litige et la Cour de céans ne saurait donc entrer en matière à ce sujet. Au demeurant, les constatations cantonales, qui lient le Tribunal fédéral (<ref-law>), ne portent pas sur les faits déterminants pour l'application de l'<ref-law>.
3. Il résulte des considérations qui précèdent que le recours doit être déclaré mal fondé dans la mesure de sa recevabilité.
Les frais et dépens sont mis à la charge du recourant, qui succombe (art. 66 al. 1 et 68 al. 1 et 2 LTF). Il se justifie toutefois de prendre en compte le caractère très succinct de la réponse de l'intimée. L'art. 8 al. 2 du règlement sur les dépens alloués à la partie adverse et sur l'indemnité pour la représentation d'office dans les causes portées devant le Tribunal fédéral (RS 173.110.210.3) permet de réduire les dépens en cas de disproportion manifeste entre le taux applicable en principe et le travail effectif de l'avocat. En application de cette disposition, il convient de réduire l'indemnité de base pour la valeur litigieuse en cause; les dépens à la charge du recourant se monteront à 500 fr.

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 à 3'000 fr., sont mis à la charge du recourant.
3. Le recourant versera à l'intimée une indemnité de 500 fr. à titre de dépens.
4. Le présent arrêt est communiqué aux parties et au Tribunal cantonal du canton de Vaud, Cour d'appel civile.
Lausanne, le 19 octobre 2011
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Klett
Le Greffier: Piaget