Hereditary Base Change
Python 2, 55
H=lambda b,c,n,s=0:n and n%b*c**H(b,c,s)+H(b,c,n/b,s+1)

A recursive solution. Like the recursive algorithm to convert between bases, except it recurses on the exponent as well.
We split n into two parts, the current digit n%b, and all other digits n/b. The current place value is stored in the optional parameter s. The current digit is converted to base c with c** and the exponent s is converted recursively. The remainder is then converted the same way, as +H(b,c,n/b,s+1) but the place value s is one higher.
Unlike base conversion, hereditary base conversion required remembering the current place value in the recursion for it to converted.
For ease of reading, here's what it looks like when b and c are fixed global constants.
H=lambda n,s=0:n and n%b*c**H(s)+H(n/b,s+1)