This study shows that affect-adaptive computer tutoring can significantly improve performance on learning efficiency and user satisfaction. We compare two different student uncertainty adaptations which were designed, implemented and evaluated in a controlled experiment using four versions of a wizarded spoken dialogue tutoring system: two adaptive systems used in two experimental conditions (basic and empirical), and two non-adaptive systems used in two control conditions (normal and random). In prior work we compared learning gains across the four systems; here we compare two other important performance metrics: learning efficiency and user satisfaction. We show that the basic adaptive system outperforms the normal (non-adaptive) and empirical (adaptive) systems in terms of learning efficiency. We also show that the empirical (adaptive) and random (non-adaptive) systems outperform the basic adaptive system in terms of user perception of tutor response quality. However, only the basic adaptive system shows a positive correlation between learning and user perception of decreased uncertainty.