Are vectors truly independent of coordinate systems? I have been told to think of vectors as existing independent of a coordinate system. This means that the magnitude of a vector should be independent of any coordinate system we choose. Galilean transformations of the form
$$ x' = x - vt $$
do not preserve the magnitude of the velocity vectors however.  How is it possible to have a vector that has a different magnitude in a different coordinate system?
 A: 
I have been told to think of vectors as existing independent of a coordinate system.

Yes. Because vectors represent physical facts. That thing is halfway between those two things. This other object is moving directly toward Toledo. And so on.
But not things like 'it's x-coordinate is +7 meters' which isn't just a fact about the thing but one that entangles the choice of origin and orientation of the axes into the description. There is no reason to expect a fact that depends on the origin to be independent of the origin. Nor a priori any reason to expect a fact that depends on the orientation of the axes to be independent of that orientations.
Which leads us to:

This means that the magnitude of a vector should be independent of any coordinate system we choose.

No. The physical fact represented by the vector remains the same, but the numeric values used top represent that fact depend on how you chose to measure them (and 'an agreement on how to measure positions' is a reasonable definition of a coordinate system).
Now there are numeric facts about quantities that are independent of certain transformation of coordinate systems. The magnitude of Cartesian vectors are invariant on rotations of the coordinate system. The magnitude of Lorentz vectors are independent of those rotations and of boosts. And so on. But the statement quoted here over generalizes that.

How is it possible to have a vector that has a different magnitude in a different coordinate system?

When positions are treated as vectors positions (which is often done in introductory courses) they are displacements from the origin. But that makes it explicit that changing the origin will change the vector that you use. A Galilean transform is one that represents a continuously changing origin, so positions and their derivatives may not be invariant on such transformations.
A: A coordinate system is not the same as a frame of reference.
A frame of reference is basically a solid considered immobile, so a point and three axes.
A coordinate system relies on a frame, and is used to determine the position of a point.
As Steeve explained, once a frame is chosen,

Choosing a different reference to describe objects in this space does not change any property of the object or of the space. It is analogous to looking from a different perspective or to talking about it in another language. The magnitude is the same regardless.

Vectors are independent of the coordinate system. They depend of the frame, though, and Galilean transform changes the frame of reference.
However forces are independent of the frame of reference!
A: Positions are not vectors. $x$ isn't a vector. There are two things you can do to vectors: add them together and scale them. It makes no sense to talk about the position of Washington DC plus the position of New York City, or the position of Washington DC times $2$.  What we can do is arbitrarily choose a point and consider the vector produced by the difference between two points. However, the resulting vector depends on the arbitrary point we chose which we usually call the origin. Any transformation that changes the origin will change the vector that represents a point. Of course, the point doesn't change. New York City doesn't move if I decide to use the South Pole as the origin instead of the North Pole. Velocities are already vectors since they correspond to (the limit of) the difference between two points.
Let $x$ be the point we're interested in and $O$ be the arbitrarily chosen origin.  Then there is a displacement vector $\mathbf r = x - O$. $x$ is then $\mathbf r + O$. If we keep the distinction between $x$ and $\mathbf r$ there is no confusion. $\mathbf r$ is independent of the origin. "226 miles northeast", as in "drive 226 miles northeast", means the same thing no matter where you are or what you call the origin. (At least on a plane. On a globe things are more subtle. The surface of a globe isn't an affine space. See the next paragraph.) $x$ is also independent of the origin. What isn't invariant is that $-\mathbf r + x$ is whatever we're currently calling "the origin". If we change the origin to $O' = \mathbf r' + O$ then we have $x = \mathbf r - \mathbf r' + O'$. If we want to know what $x - O'$ is we get $\mathbf r - \mathbf r'$. Another way of formulating this is to say we have a function, $f$, that assigns "position" vectors to points. This is (part of) our coordinate system. Our original function is $f(y) = y - O$ and we have $f(x) = \mathbf r$. Changing coordinate system means picking a different function, $g$. In the above case, $g(y) = y - O'$. Now $g(x) = \mathbf r - \mathbf r'$. So what changes when we change coordinate system is not the point $x$ or the vector $\mathbf r$, but the assignment represented by the function $f$. In this case, we can represent the transformations from the old "position" vectors to the new "position" vectors by subtracting the vector $\mathbf r'$. More complicated coordinate changes may lead to more complicated and subtle transformations. For example, $f(y) = 1000(y-O)$ might represent a change from kilometers to meters. Obviously this doesn't make things 1000 times farther away. Instead, this coordinate change has a compensating change to our notion of length, namely that it takes 1000 units in the new system to equal the same as 1 in the old. In other words, we have a conversion factor $1000\frac{\text{m}}{\text{km}}$, i.e. a vector with a magnitude of 1000 in our new system, that is it's 1000m long, is the same as a vector with a magnitude of 1 in our old system, that is it's 1km long. We will always have such compensating changes for any well-behaved change of coordinates (technically called a diffeomorphism). This is just a reflection of the fact that changing how we label parts of reality doesn't change reality.
Technically, a space where there's a well-defined notion of "difference between two points" is called an affine space. There's a more general notion called a torsor. Many notions in physics are more accurately thought of as torsors/affine spaces.  For example, an orientation in a plane is a torsor. It doesn't make sense to compose orientations, but we can consider "ratios" which we call rotations that take one orientation into another. What does northeast composed with north mean? Nothing, it's nonsense, but it's perfectly reasonable to talk about a 45° rotation composed with a 90° rotation producing a 135° rotation.
Unfortunately, much of the physics literature – especially early on – conflates affine spaces and vector spaces (and other torsors with their groups) leading to this sort of confusion and similar ones. I recommend the link I gave earlier for torsors.
A: One thing that may cause some confusion is that there are some differences between the way physicists tend to think about vectors and scalars and the way mathematicians tend to think about them. Physicists tend to think about them in this way:


*

*A 3-vector is a vector that transforms under a change of basis in the
same way as a spatial displacement.

*A 4-vector is a vector that transforms under a change of basis in the
same way as a spacetime displacement.

*A scalar is a quantity that does not change at all under a change of
basis.


Based on these ideas, I think it's helpful to introduce the idea of what I call an "incomplete object," or IO. An IO is a mathematical object that doesn't contain enough information to allow you to transform it. Suppose that I go and visit Gettysburg and stand in front of the brass plaque marking the site of the battle. I could say that I have a displacement vector $\Delta\textbf{x}=0$ between my present position in space and the position where the fighting happened. But of course this is all under the assumption that the earth is at rest. There is certainly a Galilean frame of reference in which $\Delta\textbf{x}=0$, but there are other frames in which $\Delta\textbf{x}\ne0$. This $\Delta\textbf{x}$ is an IO in the context of Galilean transformations. Suppose I tell you that $\Delta\textbf{x}=0$ in a certain frame, and then ask you to find the value of $\Delta\textbf{x}$ in some other frame, say, a frame moving toward Sirius at $10^5$ m/s. This is not enough information. In order to carry out the calculation, you would also need to know the time between the battle of Gettysburg and the present day. To make the displacement not be an IO, we would need to change it into a 4-vector.
The issue with velocity 3-vectors is basically the same as the issue with displacement 3-vectors. A velocity 3-vector is just a displacement divided by a time, so it's an IO under Galilean transformations. Relativistically, we make use of velocity 4-vectors (which have an arbitrary normalization), and these 4-vectors do transform appropriately under a Lorentz transformation (although they do not combine according to vector addition in relative motion).
Another nice example of an IO has to do with the usual method for calibrating the magnetic compass built into some handheld GPS units. The device's instructions tell you to hold it in a horizontal plane and slowly rotate 360 degrees. Because the device believes in rotational invariance, it knows how $B_x$ and $B_y$ should transform, and if it finds that $\sqrt{B_x^2+B_y^2}$ doesn't stay constant, it can recalibrate itself to eliminate the discrepancy. But if you later tilt the device so it isn't in a horizontal plane, it will get sad and confused. This tells you that $(B_x,B_y)$ is an IO, and you need to extend it to $(B_x,B_y,B_z)$.
Another example of an IO is charge density $\rho$. To make it a complete object, you need to extend it to the current 4-vector $(\rho,\textbf{j})$.
One thing to watch out for in Galilean relativity is that there is no metric. There is no unified system of measurement that measures both time and space. Therefore although you can make displacement and velocity vectors into Galilean 4-vectors, which are god-fearing complete objects rather than IOs, you can't talk about the magnitude of a Galilean 4-vector.
