The problem with the word terrorist and its formal definition as outlined in the (very good) answer by user4012 is that the word usually carries negative connotations while the formal definition tries to resort to facts that can be established. The formal definition and the general usage and connotations of the world can lead to conflicting outcomes with one group applying the label 'terrorist' while the other vehemently rejects it.
To illustrate my point, allow me to point to two figures of German history: Georg Elser and Claus Schenk Graf von Stauffenberg.
In 1939 the former had decided to use Hitler's annual speech in the Bürgerbräukeller to attempt an assassination. Over months he hollowed out a column behind the speaker's stage and deposited explosives inside. They were connected to a time-detonator device and set to go off at 9.20 pm on the evening of the 8th November 1939. In normal years, Hitler would still be speaking or at least present in the hall at that time but he left earlier that year. When the bomb exploded, the pillar was completely destroyed, parts of the ceiling collapsed, 8 people died and 57 were injured. Elser was working alone.
In 1944 the latter who was a high-ranking military officer decided to bring a hidden bomb into the conference room of the Führer headquarters to assassinate Hitler. He deposited his briefcase with the explosives on the floor next to a table where Hitler was sitting and left the room due to an alleged phone call. The bomb exploded and ultimately killed 4 people and severely injured 9 more. Stauffenberg was part of a larger group of conspirators.
Using the formal definition, both of these acts could be classified as terrorism. The former due to the large number of civilian causualties and victims, the latter additionally because it was a conspiring group. The Nazis had the perpetrators of both attacks arrested and subjected to show trials. While the word terrorist was not in that common use in German at the time and they were thus labelled high traitors, it would be reasonable to assume that nowadays the Nazis would describe them as (evil) terrorists.
Nowadays both these attempts are classified quite differently. They are seen as resistance against the Nazi dictatorship from among the citizenry (Elser) and the military (Stauffenberg). The general idea (assassinating Hitler to end/prevent the Nazi terror and war) is typically seen in a positive light. Despite fitting the formal definition, it is highly unlikely that anybody nowadays would use the word terrorist to describe these people due to the word's negative connotations.
Akin to the difference between a revolution and a rebellion, whether or not somebody is classified as a terrorist by the general public of a certain country often depends on which side they were fighting on and how much their cause is seen as morally good (and to some extend whether the side won). The closer one gets to the present, the more applying the label depends on in-group versus out-group. Thus, a group that is fighting for a cause which itself sees as morally good will typically reject the 'terrorist' label emphatically, while those parts of the general population which do not agree with this cause will be far more likely to apply it.
On the other hand, the more a group's action becomes history the more likely it becomes that the 'terrorist' label (or lack thereof) becomes accepted within the country – but whether a particular person is seen as morally good (not a terrorist) or not (terrorist) can vary between countries.
When we apply the above thoughts to Nelson Mandela, we immediately run into problems. Whether or not Mandela committed (personally or was responsible for) any acts that fit the formal defintion, he is generally seen as the iconic figure ending apartheid in South Africa. In morality terms, it is rather difficult to come up with a cause that would be considered morally good by a greater majority. However, this success was the result of decades of action in some form or another. Thus, actions committed in the past in the attempt to further that morally good goal must be considered part of the fight.
This immediately puts us into a dilemma whether we want to apply a negatively connotated label to a person supporting such a cause even though it fits the formal definition. The stronger people agree with his cause as being morally good, the more they want to reject the morally bad label of terrorist to him or his actions in the past.
I see no way to resolve this issue without rejecting at least one of the two usages of the word.