What a country should not apologize for is a basically sound foreign policy. And Clinton unfortunately did that as well--though it drew less attention than his other comments. In his Uganda speech, before the part about slavery, Clinton said:
In our own time, during the Cold War, when we were so concerned about being in competition with the Soviet Union, very often we dealt with countries in Africa and in other parts of the world based more on how they stood in the struggle between the United States and the Soviet Union than how they stood in the struggle for their own people's aspirations to live up to the fullest of their God-given abilities.
The president speaks here as if the battle against communism were an overheated World Cup match, rather than itself a struggle for democracy and human rights. Even when Realpolitik led the United States to side with dictators and oppressors, it was in the service of maximizing democracy and human rights in the world at large—a goal we in fact achieved. Every Cold War decision to put U.S. interests ahead of "people's aspirations" in individual countries may not be defensible, but the general policy is one we needn't apologize for. And by the way, the Cold War did not always define American policy in Africa. Well before the fall of communism, Congress passed comprehensive sanctions against the apartheid regime in South Africa. We did this even though the white South African government was a staunch U.S. ally in the Cold War, while Nelson Mandela's African National Congress had extensive Communist and Soviet ties.
As it happens, that subject came up during Clinton's stop in South Africa, when Mandela publicly refused to apologize for the ANC's Realpolitik alliances. It is debatable whether friendships with Libya and Cuba actually serve South Africa's interests today. But Mandela is right not to apologize for having accepted help from various malefactors, including the Soviet Union, during the liberation struggle—when actual support from the United States came very late. Like the U.S. in the Cold War, the ANC made reasonable choices under circumstances in which moral purity wasn't an option.