There is another answer brought in the name of Ram Elimelech. He says that when the Torah explicitly permitted something the Rabanan cannot make a universal prohibition that will apply everywhere. They can, however, make a prohibition for their community. He explains that Rabbeinu Gershom had made this cherem only on the community where he presided. In fact, the Shulchan Aruch (Even Haezer, siman 1:10) says that this takanah was not accepted in many communities in Spain.
In conclusion, Rabbenu Gershom was allowed to make this cherem either because he did not create an issur in doing so, because the Torah did not explicitly permit marrying more than one woman, or because his issur was not intended to affect everyone universally.