The metric is not always in the form
$$g^{\mu\nu}=\begin{pmatrix} -1&0&0&0\\
0&1&0&0\\
0&0&1&0\\
0&0&0&1 \end{pmatrix}$$
If you change your coordinate systems by rescaling the $x^0$ axis by $1000$, the metric will be
$$g^{\mu\nu}=\begin{pmatrix} -1000^2&0&0&0\\
0&1&0&0\\
0&0&1&0\\
0&0&0&1 \end{pmatrix}$$
and the inverse metric will be
$$g_{\mu\nu}=\begin{pmatrix} \frac{-1}{1000^2}&0&0&0\\
0&1&0&0\\
0&0&1&0\\
0&0&0&1 \end{pmatrix}$$
And raising and lowering must be done with these objects.
In general if you have an arbitrary coordinate change $q^\mu=F^\mu(x)$, then the components of the vectors will change from $X^\mu$ to $\frac{\partial F^\mu(x)}{\partial x^\nu}X^\nu$, where a sum over indices appearing twice is implied.
The metric and inverse metric also transform to:
$$g^{\alpha\beta}\frac{\partial F^\mu(x)}{\partial x^\alpha}\frac{\partial F^\nu(x)}{\partial x^\beta} \qquad g_{\alpha\beta}\frac{\partial F^\alpha(x)}{\partial x^\mu}\frac{\partial F^\beta(x)}{\partial x^\nu}$$
And you can find, for example if you switch to spherical coordinates, that the metric no longer is constant on your space.
You're dealing with different geometric objects: Tangent vectors, which can be realized as equivalence classes of curves, and cotangent vectors, which can be realized as equivalence classes of real-valued functions (think differentials).
There's a natural linear pairing operation between these objects: Compose a curve and a function, and you get a map $\mathbb R\to\mathbb R$. Take it's derivative at the point in question, et voilà. This pairing operation allows us to consider the spaces as 'dual', and in particular identify the cotangent space with the space of linear functionals on the tangent space.
Given a coordinate system on a manifold, the coordinate lines are curves, yielding a basis of the tangent space, whereas the components of the coordinate chart are functions, yielding a basis of the cotangent space. It's easy to show that these bases are algebraically dual, ie their pairing yields the Kronecker delta.
On (pseudo-)Riemannian manifolds, there's additionally a metric tensor $g$, a non-degenerate bilinear form. This tensor induces an isomorphism $g^\flat:v\mapsto g(v,\cdot)$ from the tangent to the cotangent space ('lowering the index'), with an inverse map $g^\sharp$ ('raising the index').
The map $g^\sharp$ can be used to pull back our basis of the cotangent space onto the tangent space, yielding the reciprocal basis. The components of a vector $v$ relative to the reciprocal basis of the tangent space are the same as the components of the covector $g^\flat v$ relative to the dual basis of the cotangent space. This makes it possible to conflate vectors and covectors, but that's considered a mostly bad idea nowadays.
Having said all that, now on to your actual question:
But if I were to take a vector $V^{\mu}$ and lower the index to a covector $V_{\mu}$ in flat space, it most certainly would not be the complicated change of basis matrix shown in the example. Am I missing something here?
The Minkowski metric is that 'complicated change of basis matrix' - it's just that you're dealing with an orthonormal basis, which makes it simple.
Best Answer
Yes, the statement holds true in general relativity as well. However, as we need to deal with tensors of higher and in particular mixed order, the rules of matrix multiplication (which is where the idea of the representation via row- and column-vectors comes from) are no longer sufficiently powerful:
Instead, the placement of the index determines if we are dealing with a contravariant (upper index) or a covariant (lower index) quantity.
Additionally, by convention an index which occurs in a product in both upper and lower position gets contracted, and equations must hold for all values of free indices.
If the given metric is non-Euclidean (which is already true in special relativity), mapping between co- and contravariant quantities is more involved than simple transposition and the actual values of the components in a given basis can change, eg: $$ p^\mu = (p^0,+\vec p)\\ p_\mu = (p^0,-\vec p) $$ and in general: $$ p_\mu = g_{\mu\nu}p^\nu $$ where $g_{\mu\nu}$ denotes the metric tensor and a sum $\nu=1\dots n$ is implied.