Time complexity of base conversion
Conversion from base $b^k$ to base $b^l$ can be done by reading the original number in chunks of length $\mathrm{lcm}(k,l)/k$, and converting each such chunk into $\mathrm{lcm}(l,k)/l$ digits in the new base. For fixed $b,k,l$, this is linear time.

There is a non-trivial algorithm for base conversion in time $O(M(n)\log n)$, where $M(n)$ is the time it takes to multiply two $n$-bit numbers, $n$ is the length of the number (in digits), and the two bases are fixed. See for example page 14 of these notes by Brent.

The question you are asking is, for fixed $b_1,b_2$ which cannot be written in the form $b^k,b^l$, whether there exists a linear time algorithm for converting from base $b_1$ to base $b_2$. One possible approach to show that this is impossible might be by reducing multiplication (or any other equivalent operation, such as division) to base conversion for some fixed constant bases -- but it's not clear if it is in fact possible to build such a reduction or not. I don't believe the question has been asked in the literature.