Elsewhere on this site, avi cited sources to the effect that, contrary to the Bavli (M'gila), the events recounted in the book of Ester took place after the second bes hamikdash was built. Do any rishonim (or earlier Judaism sources) say as much, thus lending credibility to the claim? (A number of rishonim, in their commentaries on Nach, did not hesitate to argue with the Bavli's reading of Nach.) I seek not sources who merely could be interpreted as implying as much (after all, one could say the p'sukim themselves imply as much), but sources who actually say so.
The most commonly held opinion is that the story of Esther took place after the foundation of the 2nd Beis HaMikdash was built, but before the building was completed. (See Artscroll on Ezra, among others; Medrash Esther Rabba; etc.) The building process was halted by royal edict in the middle of the construction. The exact timeline is discussed in depth by the commentaries on Ezra, where the text itself gives many details of the sequence of events.
Therefore, one could correctly say that the story of Purim took place after the [start of the] building of the 2nd Beis HaMikdash, before the [end of the] building of the 2nd Beis HaMikdash, or during the building of the 2nd Beis HaMikdash. It's just a matter of semantics.