They are representing n to mean 2 different things. In this case, n is meant to represent a value passed in to the algorithm. The problem is that complexity is usually expressed relative to size of the input, which in case of this algorithm is log(n) = m bits. This makes the exponentiation version actually linear in terms of bits needed to represent the input.
It's like saying that an algorithm that accepts n x n matrix and takes O(n) steps to compute something is "linear" - it's not linear, because the size of the data is m = n^2, which makes it O(sqrt(m)).
