Why is the Change of Basis map unique?

Remember that any linear map on any linear space $\;V\;$ is uniquely and completely determined once we know its action on any basis of $\;V\;$ ...and that's all.

If you want to do this proof, suppose there's another map $\;Q:V\to V\;$ s.t. it coincides on "the old basis" $\;\mathcal B\;$ with $\;P:\;\; Qv_i=Pv_i\;\;\forall\,i=1,2,...,n\;$ , then (using linearity of the maps), for any

$$v=\sum_{k=1}^n a_iv_i\in V\;,\;\;Qv=\sum_{k=1}^na_iQv_i=\sum_{k=1}^n a_iPv_i=Pv$$

so $\;Q\equiv P\;$.

A basis is an ordered set of vectors that are independent and generates the whole vector space. If you have two basis $\mathcal B$ and $\mathcal C$ as in your post, then a change of basis $f$ from $\mathcal B$ to $\mathcal C$ must satisfy $f(v_i)=u_i$ for $i=1,\ldots,n$ (in this precise order). There is a unique map satisfying this requirement by a theorem stating that if a linear map is defined over a basis then it is uniquely defined over the whole space. Since the requirement fix the images of the elements of the basis $\mathcal B$ then there is only a unique map that satisfies those conditions.