BattleTech suggestion
Number of Territories: 40 to 50
Special Features: To be determined
What Makes This Map Worthy:
Although it's much less popular than it was 20+ years ago, the BattleTech universe (created by FASA Corporation) has a long history in gaming. There was a hex-based board game, an RPG, a collectible card game, a comic line, an animated TV series, an early PC game, and others).
The map would be based on the traditional 2-D circular depiction of the "Inner Sphere" showing the interplanetary dominions of the great Houses (Davion, Kurita, Liao, Marik, Steiner) surrounding Terra. Part of the map would also show the four initial invading Clans from the Deep Periphery (Wolf, Jade Falcon, Ghost Bear, Smoke Jaguar).
Many images of the BattleTech map layout are available on the net... just search "battletech map images".
For added complexity, special rules might include other elements of the BattleTech universe -- such as ComStar, mercenary holdings, and the Outer Periphery regions.
Please note: I don't know anything about copyright issues -- but I see that there are other maps on ConquerClub that are based on existing franchises (Midkemdil, Tamriel, Discworld, etc.).