Commanding a small army has a great feel to it, I would not deny a PC to have followers. One PC has finally received their Enhanced Leadership ability and now has 40 NPC followers. This is fairly new to our group, we've always run traditional party campaigns. Any suggestions for keeping a campaign challenging and fun for all PCs while utilizing followers from the Leadership feat?

I will certainly use the mass combat rules to have skirmishes and battles, but I don't want to overdo it and turn it into a strategy wargame or leave out other PCs, who are not leaders. (Until the scenario where he gets to conquer a country at least!)

I also don't want to have constant scenario's where the Leader's followers are not available for him to use as a resource or just background decoration, just so I can give the other PCs challenges (traveling can be easier now without random animal encounters or sending off the lackies to take care of it)
Absolutely -- bringing some of the troops along lets you make the combats seem more deadly without actually putting the characters at any greater risk. Think of the followers as Red Shirts, not to be slaughtered wholesale, but to die when it's important to make a point with a good guy's death.

This is also a great opportunity to develop one or two NPCs, either common followers or officers of some sort, whom the PC can trust to handle some details and free up the rest of the heroes to do important work. This is an opportunity to separate the PC from his followers without seeming unfair -- they are off following orders to make the PCs' lives easier.

Unless the PC has been hired as a mercenary commander, try not to bring along more than a few people as guards, or it will get out of hand. Somebody needs to stay behond to watch the stronghold, keep the men in line, and do all the other little tasks. If the player insists on bringing large numbers of his PC's followers along all the time, make sure that they get in the way, die miserably, get in trouble, and lose morale until the guy takes a hint.