Faits:
A. A.a A._, né en 1951 à Z._, et B._, née en 1951 à Y._, se sont mariés le 21 juillet 1973 à Vendlincourt. Deux enfants sont issues de cette union, C._ et D._.
A.b Après cinq ans de séparation, les époux A._ ont déposé, le 30 mai 2001, une requête commune en divorce, avec accord complet sur les effets accessoires, devant le Tribunal de première instance de Genève. Leurs filles étaient toutes deux majeures.
Le 22 novembre 2001, le Tribunal de première instance de Genève a prononcé le divorce des parties et entériné leur accord, notamment l'engagement de l'époux de contribuer à l'entretien de son épouse par le versement d'une pension mensuelle de 1'000 fr. jusqu'à l'achèvement des études de leur fille, D._, ou jusqu'à la cessation du versement de la contribution due à cette dernière; dès la survenance de l'un ou l'autre de ces deux événements, la contribution due à l'épouse devait être augmentée à 1'500 fr. par mois jusqu'à la retraite de celle-ci en 2016.
Lors du divorce, A._ réalisait un revenu mensuel net de 9'760 fr. et assumait des charges à hauteur de 5'862 fr. 50, contribution due à l'épouse non comprise. B._ percevait, quant à elle, un salaire mensuel de 5'650 fr.; elle et sa fille, avec laquelle elle vivait, devaient faire face à des charges mensuelles de 5'566 fr., la pension de A._ en faveur de sa fille s'élevant au moment du divorce à 1'500 fr. À la fin des études de celle-ci, les parties avaient arrêté leurs charges respectives à 5'612 fr. 50, contribution de l'épouse comprise, pour le mari et à 5'000 fr. 50 pour l'épouse. Les parties avaient ainsi convenu qu'avec une contribution de 1'500 fr., B._ jouirait d'un disponible de 2'149 fr. 50 par mois.
B. B.a Le 29 mars 2011, A._ a requis, devant le Tribunal de première instance de Genève, la modification du jugement de divorce. Invoquant une modification notable et durable des circonstances, il a conclu à ce que la contribution en faveur de B._ soit supprimée, subsidiairement qu'elle soit suspendue pour une durée de deux ans à compter du dépôt de la demande et à ce que la défenderesse soit condamnée à lui restituer toutes les contributions versées depuis lors.
Une convocation à l'audience de conciliation et de comparution personnelle du 6 juin 2011 a été adressée à «B._». B._, qui a repris son nom de jeune fille l'année suivant le divorce, n'a pas pu la retirer à la poste. Elle a cependant été informée par A._ de l'audience puis a reçu une convocation à son nom le 27 mai 2011. Elle s'est fait représenter à l'audience du 6 juin 2011 et a obtenu une prolongation du délai imparti pour répondre ainsi que la fixation d'une nouvelle audience de suite de comparution.
Par jugement du 29 novembre 2011, le Tribunal de première instance de Genève a rejeté la demande de A._.
B.b Statuant sur appel de ce dernier, la Cour de justice du canton de Genève a confirmé ce jugement, par arrêt du 14 septembre 2012.
S'agissant de la situation financière des parties, il a été retenu en première instance comme en appel que A._ réalisait, malgré la prise de retraite anticipée, un revenu mensuel de 11'258 fr., supportant des charges de 4'848 fr., et que B._ percevait un salaire de 6'457 fr. pour des charges mensuelles de 3'657 fr.
C. Le 18 octobre 2012, A._ exerce un recours en matière civile au Tribunal fédéral contre cet arrêt concluant à son annulation et à la modification du jugement de divorce du 22 novembre 2001 en ce sens que la contribution d'entretien en faveur de B._ est supprimée, subsidiairement suspendue pour une durée de deux ans, dès le dépôt de la demande, la défenderesse étant condamnée à lui restituer toutes les contributions versées depuis lors. À l'appui de ses conclusions, le recourant se plaint d'une violation de l'<ref-law> ainsi que d'une constatation inexacte et arbitraire des faits.
Invitée à se déterminer sur le recours, B._ a conclu à son rejet par mémoire du 30 janvier 2013.

Considérant en droit:
1. Le recours a été interjeté dans le délai légal (<ref-law>), contre une décision finale (<ref-law>), prise en dernière instance cantonale et sur recours par le tribunal supérieur du canton de Genève (<ref-law>), dans une affaire matrimoniale (<ref-law>), dont la valeur litigieuse est supérieure à 30'000 fr. (<ref-law>). Le recourant a par ailleurs pris part à la procédure devant l'autorité précédente et démontre un intérêt digne de protection à la modification de la décision attaquée (<ref-law>), de sorte que le recours en matière civile est en principe recevable.
2. 2.1 Saisi d'un recours en matière civile, le Tribunal fédéral applique le droit d'office (<ref-law>) sans être lié ni par les motifs de l'autorité précédente, ni par les moyens des parties; il peut donc admettre le recours en se fondant sur d'autres arguments que ceux invoqués par le recourant, comme il peut le rejeter en opérant une substitution de motifs (<ref-ruling> consid. 2.2). Il ne connaît cependant de la violation des droits fondamentaux que si ce grief a été soulevé et motivé par le recourant (<ref-law>; <ref-ruling> consid. 3.2; <ref-ruling> consid. 1.4.2). Le recourant doit ainsi indiquer précisément quelle disposition constitutionnelle a été violée et démontrer, par une argumentation précise, en quoi consiste la violation (principe d'allégation; Rügeprinzip; principio dell'allegazione; <ref-ruling> consid. 1.4; <ref-ruling> consid. 1.4.2).
2.2 Le Tribunal fédéral ne peut s'écarter des faits établis par l'autorité précédente que si ceux-ci l'ont été de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>) et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-law>). Le recourant qui soutient que les faits ont été établis d'une manière manifestement inexacte (<ref-law>), c'est-à-dire que les constatations de fait sont arbitraires au sens de l'art. 9 Cst. (ATF <ref-ruling> consid. 1.2.2), doit satisfaire au principe d'allégation susmentionné (consid. 2.1).
3. 3.1 En substance, la cour cantonale a considéré que les parties, qui avaient prévu l'allocation d'une contribution d'entretien jusqu'à la retraite de l'intimée en 2016, avaient pris en compte un concubinage de l'épouse - qui était prévisible - lors de la fixation de sa contribution d'entretien, faute de quoi elles auraient expressément convenu une suppression de la pension en faveur de l'intimée dans un tel cas. Elle a en outre précisé que le recourant, qui avait eu connaissance du concubinage à la fin de l'année 2001, n'avait pas pour autant demandé la suppression de la contribution jusqu'ici. Elle en déduit que les parties n'avaient ni convenu ni voulu une telle suppression en cas de concubinage de l'intimée. De plus, la juridiction a considéré que l'amélioration de la situation financière de l'intimée, comme celle encore plus importante du recourant, était prévisible, compte tenu de l'évolution des salaires, et n'était pas notable au point de justifier une modification des engagements pris par le recourant envers son ex-épouse.
3.2 Se référant à la requête commune en divorce et à la convention sur les effets accessoires - plus précisément à la comptabilisation des charges de l'intimée et à l'augmentation de la contribution une fois achevées les études universitaires de D._, qui vivait avec sa mère et participait aux charges du ménage -, le recourant fait valoir que les parties avaient prévu que l'intimée vivrait seule et qu'il n'avait jamais été question qu'il continue à contribuer à l'entretien de son ex-épouse en cas de remariage ou de concubinage qualifié. Dans de telles circonstances, on ne saurait déduire, selon lui, que le concubinage de l'intimée était prévisible au moment du divorce, ni que les parties n'auraient pas voulu supprimer la rente pour ce motif. Il fait également valoir que, au moment du divorce, soit peu de temps après l'entrée en vigueur du nouveau droit, les parties, non représentées par un avocat, considéraient que, comme sous l'ancien droit, le concubinage qualifié était assimilé au remariage en ce qui concerne la suppression de l'obligation d'entretien, la précision jurisprudentielle n'étant intervenue qu'en 2006. Enfin, il avance que la situation financière des parties a également connu une modification durable notable et imprévisible en tant que ses revenus se sont réduits de manière conséquente - précisant que la cour n'avait arbitrairement pas pris en compte qu'il ne réalisait plus de revenu complémentaire depuis le 31 août 2012 - et que l'intimée a vu ses charges diminuer.
3.3 L'intimée se prévaut tout d'abord de la nullité de l'assignation et de l'irrecevabilité de la demande dans la mesure où celle-ci la désigne sous le nom de «B._». Pour le surplus, elle fait valoir que la situation financière des parties ne s'était pas modifiée dans une mesure justifiant une modification du jugement de divorce et que son concubinage ne pouvait être considéré comme un événement exceptionnel et imprévisible auquel les parties n'auraient pas pensé lors de l'établissement de la convention sur les effets accessoires de leur divorce. Elle précise que si tel avait été le cas, le recourant n'aurait pas attendu dix ans pour requérir la suppression de la contribution.
4. A titre liminaire, il y a lieu de constater la recevabilité de la demande et d'écarter le grief de nullité soulevé par B._. L'inexactitude purement formelle dans la dénomination de la défenderesse contenue dans la demande et la première convocation à l'audience du 6 juin 2011 - laquelle n'a pu être retirée à la poste - a été corrigée conformément à la jurisprudence en la matière, dès lors qu'il n'existait aucun doute sur l'identité de celle-ci, laquelle résultait d'ailleurs de l'objet du litige (cf. <ref-ruling> consid. 1b; <ref-ruling> consid. 3a; arrêt 4A_35/2008 du 13 juin 2006 consid. 2.6). Aussi, une nouvelle convocation lui a été notifiée et la demande a été rectifiée de manière manuscrite. De plus, ce vice de forme n'a pas été préjudiciable à l'intimée puisqu'elle a pu se faire représenter à l'audience du 6 juin 2011 et a obtenu une prolongation du délai pour répondre ainsi que la fixation d'une nouvelle audience de suite de comparution. Ce serait ainsi faire preuve de formalisme excessif que de contraindre le recourant à déposer une nouvelle demande aux seules fins de rectifier la dénomination de la défenderesse.
5. La question litigieuse est principalement celle de savoir si le concubinage de l'épouse constitue un motif de suppression, subsidiairement de suspension, de sa contribution d'entretien en application de l'<ref-law> ou si, comme retenu par la cour cantonale, les parties avaient tenu compte de cet élément, jugé prévisible, lorsqu'elles avaient prévu une pension jusqu'à l'âge de la retraite.
5. La question litigieuse est principalement celle de savoir si le concubinage de l'épouse constitue un motif de suppression, subsidiairement de suspension, de sa contribution d'entretien en application de l'<ref-law> ou si, comme retenu par la cour cantonale, les parties avaient tenu compte de cet élément, jugé prévisible, lorsqu'elles avaient prévu une pension jusqu'à l'âge de la retraite.
5.1 5.1.1 Le concubinage qualifié (ou concubinage stable) du créancier de l'entretien n'entraîne pas, par application analogique de l'<ref-law> relatif au remariage, une extinction de l'obligation d'entretien (arrêt 5C.93/2006 consid. 2.1 du 23 octobre 2006 in FamPra.ch 2007, p. 154). L'<ref-law>, qui permet au juge de diminuer, supprimer ou suspendre la rente pendant une durée déterminée peut cependant trouver application lorsque le créancier vit dans un concubinage qualifié (arrêt 5C.265/2002 du 1 avril 2003 consid. 2.4 non publié aux <ref-ruling>).
Selon l'<ref-law>, la modification de la contribution d'entretien après divorce suppose que des faits nouveaux importants et durables interviennent dans la situation d'une des parties, qui commandent une réglementation différente. La procédure de modification n'a en effet pas pour but de corriger le premier jugement, mais de l'adapter aux faits nouveaux. Le fait revêt un caractère nouveau lorsqu'il n'a pas été pris en considération pour fixer la contribution d'entretien dans le jugement de divorce. Ce qui est déterminant, ce n'est pas la prévisibilité des circonstances nouvelles mais exclusivement le fait que la rente ait été fixée sans tenir compte de ces circonstances futures (<ref-ruling> consid. 11.1.1; <ref-ruling> consid. 2.7.4; arrêt 5A_93/2011 du 13 septembre 2011 consid. 6.1; 5A_845/2010 du 12 avril 2011 consid. 4.1).
5.1.2
5.1.2.1 Selon la jurisprudence, il faut entendre par concubinage qualifié (ou concubinage stable) une communauté de vie d'une certaine durée entre deux personnes de sexe opposé, à caractère en principe exclusif, qui présente une composante tant spirituelle que corporelle et économique, et qui est parfois également désignée comme communauté de toit, de table et de lit; le juge doit dans tous les cas procéder à une appréciation de tous les facteurs déterminants, étant précisé que la qualité d'une communauté de vie s'évalue au regard de l'ensemble des circonstances de la vie commune (<ref-ruling> consid. 3b; <ref-ruling> consid. 2a/aa et les références citées; arrêt 5C.265/2002 du 1 avril 2003 consid. 2.4 non publié aux <ref-ruling>). Il incombe au débiteur d'entretien de prouver que le créancier d'entretien vit dans un concubinage qualifié avec un nouveau partenaire (<ref-ruling> consid. 3b); le Tribunal fédéral a toutefois posé la présomption - réfragable - qu'un concubinage est qualifié lorsqu'il dure depuis cinq ans au moment de l'ouverture de l'action en modification du jugement de divorce (<ref-ruling> consid. 3a; <ref-ruling> consid. 1c). L'existence ou non d'un concubinage qualifié ne dépend pas des moyens financiers des concubins, mais de leurs sentiments mutuels et de l'existence d'une communauté de destins (ATF <ref-ruling> consid. 2a/aa).
5.1.2.2 La suspension ou la suppression de la contribution en cas de concubinage qualifié est possible même si la communauté de vie n'a pas encore atteint une durée de cinq ans mais présente en raison d'autres facteurs une stabilité suffisante (arrêts 5A_81/2008 du 11 juin 2008, consid. 5.4.4 et 5.5 in FamPra.ch 2008, p. 944; 5C.296/2001 du 12 mars 2002 consid. 3b/bb). Le choix entre la suspension ou la suppression de la rente, doit procéder dans chaque cas d'une pesée des intérêts, entre celui du créancier à pouvoir en bénéficier en cas de dissolution du concubinage et celui du débiteur à être définitivement libéré de son obligation d'entretien (HAUSHEER/SPYCHER, Handbuch des Unterhaltsrechts, 2010, n. 10.40; PICHONNAZ, Code civil I, Commentaire romand, n° 53 s. ad <ref-law>; SPYCHER/GLOOR, Zivilgesetzbuch I, Basler Kommentar, 2010, n° 15 ad <ref-law>). La suppression sera généralement prononcée lorsque la durée du concubinage est supérieure au délai de cinq ans (HAUSHEER/SPYCHER, ibidem; SPYCHER/GLOOR, ibidem).
5.2 En l'espèce, à l'instar du premier juge, la cour cantonale a considéré qu'en l'absence d'indice contraire, le concubinage - futur - de l'épouse était un fait prévisible, comme d'ailleurs celui de l'époux. Les parties devaient envisager que chacune d'entre elles pourrait se mettre en concubinage après leur divorce et elles auraient pu prévoir dans leur convention que dans ce cas, la contribution s'éteindrait. Comme elles ne l'ont pas fait, la cour cantonale en a conclu que les parties n'avaient ni convenu ni voulu que la contribution d'entretien soit supprimée en cas de concubinage de l'ex-épouse.
Cette argumentation est contraire au droit fédéral. Ce qui est décisif, ce n'est pas de savoir si des époux qui divorcent sont susceptibles de refaire leur vie et de vivre en concubinage avec un nouveau partenaire, mais si, lorsqu'ils ont passé leur convention, les époux ont non seulement envisagé cette éventualité, mais encore l'ont expressément réglée. L'arrêt cantonal doit donc être annulé.
5.3 Saisi d'un recours en matière civile, le Tribunal fédéral peut réformer la décision attaquée s'il dispose des éléments nécessaires pour statuer. En l'occurrence, pour décider si les parties ont réglé la question de la suppression ou suspension de la rente en cas de concubinage, il s'impose d'interpréter leur convention sur les effets accessoires du divorce ratifiée par jugement du 22 novembre 2011, sur la base des faits ressortant de l'arrêt cantonal.
5.3.1 Une convention sur les effets accessoires du divorce est une manifestation de volonté qui doit être interprétée selon les mêmes principes que les autres contrats (arrêts 5A_88/2012 du 7 juin 2012 consid. 3; 5C.52/2007 du 12 juillet 2007 consid. 2). Le juge doit recourir en premier lieu à l'interprétation subjective, c'est-à-dire rechercher la réelle et commune intention des parties, le cas échéant empiriquement, sur la base d'indices, sans s'arrêter aux expressions ou dénominations inexactes dont elles ont pu se servir, soit par erreur, soit pour déguiser la véritable nature de la convention (<ref-law>; <ref-ruling> consid. 3.3; <ref-ruling> consid. 2.3.2, 626 consid. 3.1; <ref-ruling> consid. 4.1). Ce n'est que si le juge ne parvient pas à déterminer cette volonté réelle des parties - parce que les preuves font défaut ou ne sont pas concluantes - ou s'il constate qu'une partie n'a pas compris la volonté exprimée par l'autre à l'époque de la conclusion du contrat (<ref-ruling> consid. 3.1) - ce qui ne ressort pas déjà du simple fait qu'elle l'affirme en procédure, mais doit résulter de l'administration des preuves (arrêt 5A_198/2008 du 26 septembre 2008 consid. 4.1) - qu'il doit recourir à l'interprétation objective, à savoir rechercher la volonté objective des parties, en déterminant le sens que, d'après les règles de la bonne foi, chacune d'elles pouvait et devait raisonnablement prêter aux déclarations de volonté de l'autre (application du principe de la confiance; <ref-ruling> consid. 3.3; <ref-ruling> consid. 2.3.2, 626 consid. 3.1). Ce principe permet d'imputer à une partie le sens objectif de sa déclaration ou de son comportement, même si celui-ci ne correspond pas à sa volonté intime (<ref-ruling> consid. 3.3; <ref-ruling> consid. 3.2; <ref-ruling> consid. 2.5; <ref-ruling> consid. 2.2).
5.3.2 En l'espèce, l'autorité cantonale n'a pas déterminé la volonté subjective des parties et le recourant ne s'en plaint pas. Il y a donc lieu d'examiner leur volonté objective.
Les époux ont signé leur convention sur les effets accessoires du divorce le 9 mai 2001 et l'ont produite avec leur requête commune en divorce du 30 mai 2001. Aucune clause ne règle la question de la suppression ou suspension de la rente en cas de concubinage. A cette époque-là, les époux étaient déjà séparés, mais l'épouse ne vivait pas en concubinage. Celui-ci n'a débuté qu'à la fin de l'année 2001, soit après le prononcé du divorce par le Tribunal de première instance le 22 novembre 2001. Il ressort en outre de la convention que, d'une part, les montants retenus, lors de la comptabilisation des charges de l'épouse (minimum vital et frais de logement), correspondent à ceux d'une personne vivant seule et que, d'autre part, les parties ont prévu que celle-ci continuerait à occuper seule le logement de famille. Qui plus est, les époux ont expressément convenu une augmentation de la rente dès le moment où leur fille, qui participait aux frais du ménage qu'elle formait avec sa mère, aurait achevé ses études ou ne percevrait plus de contribution de la part de son père.
Dans ces circonstances et en l'absence de disposition expresse de la convention, et alors même que la rente a été fixée pour une certaine durée, soit jusqu'à la retraite de l'ex-épouse en 2016, on ne saurait de bonne foi considérer que les époux auraient pris en considération l'hypothèse d'un concubinage futur de l'épouse et voulu que celui-ci - même qualifié - n'ait aucune incidence sur la contribution d'entretien. Le fait que le recourant ait, après avoir appris le concubinage de son ex-épouse, payé au-delà de la durée de cinq ans nécessaire pour présumer l'existence d'un concubinage qualifié, n'y change rien.
Il s'ensuit que les conditions d'une modification au sens de l'<ref-law> sont remplies.
5.4 Il reste encore à déterminer les conséquences du concubinage sur l'obligation d'entretien du recourant. En l'occurrence, la vie commune de l'intimée avec son ami avait duré près de dix ans au moment du dépôt de la demande. De plus, il n'est pas contesté que cette communauté de vie présente toutes les caractéristiques d'un concubinage qualifié au sens de la jurisprudence. Aussi, compte tenu de la durée particulièrement longue du concubinage de l'intimée, une suppression de la contribution d'entretien se justifie en l'espèce. En effet, en présence d'une relation présentant une telle stabilité, l'intérêt du débiteur à être définitivement libéré l'emporte sur celui de la créancière au maintien de la rente ou à la suspension de celle-ci. Enfin, la contribution d'entretien pouvant être supprimée en cas de concubinage indépendamment de toute amélioration de la situation financière de la créancière (arrêt 5A_81/2008 du 11 juin 2008, consid. 5.1.2 in FamPra.ch 2008, p. 944 et les références citées), il n'y a pas lieu d'examiner plus avant l'évolution des revenus et charges des parties.
Il suit de là que la contribution d'entretien en faveur de l'intimée doit être supprimée.
6. Le recourant requiert que la rente soit supprimée dès le dépôt de la demande et que l'intimée soit condamnée à lui restituer les montants perçus à titre de contribution d'entretien durant la procédure.
Le juge de l'action en modification d'un jugement de divorce peut fixer le moment à partir duquel son jugement prend effet selon son appréciation et en tenant compte des circonstances du cas concret. En principe, la jurisprudence retient, au plus tôt, la date du dépôt de la demande. Lorsque le motif pour lequel la modification est demandée se trouve déjà réalisé à ce moment, il ne se justifie normalement pas, du point de vue de l'équité, de faire remonter l'effet de la modification à une date ultérieure. Le créancier de la contribution doit en effet tenir compte d'un risque de réduction ou de suppression de la rente dès l'ouverture d'action. Selon les circonstances, il est toutefois possible de retenir une date ultérieure, par exemple le jour du jugement, notamment lorsque la restitution des contributions accordées et utilisées pendant la durée du procès ne peut équitablement être exigée (<ref-ruling> consid. 4c; arrêt 5A_290/2010 du 28 octobre 2010 consid. 9.2 in SJ 2011 I p. 177).
En l'espèce, le concubinage ayant duré près de dix ans au moment de la demande, le motif de la suppression de la rente était déjà réalisé à ce moment-là. L'intimée n'a quant à elle fait valoir aucune circonstance permettant de ne pas exiger qu'elle restitue les contributions perçues durant la procédure. En conséquence, il y a lieu de supprimer la contribution d'entretien dès le 1er avril 2011, à savoir dès le mois suivant le dépôt de la demande, et de condamner l'intimée à restituer au recourant la somme de 34'500 fr. (23 x 1'500 fr.).
7. En définitive, le recours est admis et l'arrêt cantonal est réformé en ce sens que la contribution d'entretien due par A._ en faveur de B._ est supprimée dès le 1er avril 2011 et que B._ est condamnée à restituer à A._ la somme de 34'500 fr. Les frais de justice, arrêtés à 3'000 fr., sont mis à la charge de l'intimée qui succombe (<ref-law>). L'intimée versera en outre au recourant une indemnité de dépens à hauteur de 4'000 fr. (art. 68 al. 1 et 2 LTF). Il appartiendra à l'autorité cantonale de statuer à nouveau sur les frais et dépens de la procédure cantonale (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis et l'arrêt attaqué est réformé comme suit:
1.1 La contribution d'entretien due par A._ en faveur de B._ est supprimée dès le 1er avril 2011.
1.2 B._ est condamnée à restituer à A._ la somme de 34'500 fr.
2. Les frais judiciaires, arrêtés à 3'000 fr., sont mis à la charge de l'intimée.
3. Une indemnité de 4'000 fr., à payer à titre de dépens au recourant, est mise à la charge de l'intimée.
4. La cause est renvoyée à l'autorité cantonale pour nouvelle décision sur les frais et dépens des instances cantonales.
5. Le présent arrêt est communiqué aux parties et à la Cour de justice du canton de Genève, Chambre civile.
Lausanne, le 27 février 2013
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
Le Président: von Werdt
Le Greffier: Richard