Euclidean vectors (in a $2$-dimensional space) are defined as ordered pairs of real numbers, which in a Cartesian coordinate system can be graphically represented by a directed line segment going from $(0,0)$ to a point representing said pair.
Considering that the tuples themselves ARE vectors, it would seem that if we change the position of axes of the Cartesian coordinate system (so that the angles between $x$ and $x'$ and $y$ and $y'$ axes are $45$ degrees, for example), the vector, being a tuple, will now be represented by a segment going from $(0,0)$ to wherever the tuple its end was originally assigned to is now placed, leaving its position relative to the axes unchanged.
This is not what is happening. Instead, the line segment doesn't change its position and angle toward the original $x$ and $y$ axes, so when the coordinate axes move, it has a different position relative to new axes than to old ones. What's more important, the pair the line segments end on is now different - if we had a vector which originally was $(1,1)$, and move the coordinate axes $45$ degrees counterclockwise, that point is now $(1,0)$.
Once again, these vectors are defined by tuples. A tuple is a vector. How can we call the original $(1,1)$ and the new $(1,0)$ the same vector? Why isn't the $(1,1)$ in new coordinates considered the same vector as $(1,1)$ in original coordinates?
The tuple $u=(1,1)$ is by definition an element of the space $\mathbf{R}^2$.
Now suppose we are given any two linearly independent elements of $\mathbf{R}^2$ (i.e. a basis), say $$ f_1=(2,5) , \qquad f_2=(1,2) . $$ Then we can ask the question how we can combine $f_1$ and $f_2$ to get $u$, and the answer in this case happens to be that we add minus one $f_1$ and three $f_2$: $$ u = -1 f_1 + 3 f_2 . $$ Then we say that the coordinate vector of $u$, with respect to the basis $(f_1,f_2)$, is $(-1,3)$.
Of course, $u$ is still the tuple $(1,1)$, and this is not the same tuple as $(-1,3)$. But given that we know what $f_1$ and $f_2$ are, we can equally well use the numbers $-1$ and $3$, instead of the numbers $1$ and $1$, to describe what element $u \in \mathbf{R}^2$ we are talking about.
Strictly speaking, it's abuse of language to say “after the change of coordinates, we have $u=(-1,3)$”, since it's not $u$ itself but rather its coordinate vector that is $(-1,3)$. And I think this is what you are objecting to. But still one often uses phrases like that as a convenient shorthand.
Much confusion in linear algebra classes comes from the fact that the coordinate vector is an object in $\mathbf{R}^2$, the same space as that of the object $u$ which it is describing. I think it makes life easier if one thinks of vectors as geometrical objects (“arrows”) which don't have any coordinates at all until you have specified a basis (a spanning set of linearly dependent “arrows”). Then the vector itself is an element of some geometrical space (whatever that is, exactly, but that's another question), and the coordinate vector is a tuple of numbers. And the coordinate vector depends on which basis you use; if you change to a different basis, the same geometrical vector will of course be described by a different tuple of numbers.