Suppose I have a uniform magnetic field through all of space $$\textbf{B}(x,y,z)=\hat{\textbf{z}}$$ and a charge $q$ moving at a velocity of $v\hat{\textbf{x}}$. In this frame of reference, a magnetic force will act on $q$, pushing it up (or down, but let's assume up). Suppose instead I change my frame of reference so that $q$ is stationary at the origin. In this frame of reference, there is no force to act on $q$ and it shouldn't move. Naturally, this seems inconsistent.
The normal explanation given for this from what I've seen is that the magnetic field changes into an electric field upon a change of reference so that there is still a force in the second frame of reference and the results agree. I have some problems with this though:
This doesn't explain the source of the $\textbf{E}$ field in the second frame. Where does it come from? According to Maxwell's equations, $\textbf{E}$ fields can only be produced by time-varying magnetic fields or charges. There are no charges (apart from $q$) and no time-varying magnetic fields in either frame of reference - so Maxwell's equations seem to predict a zero electric field in either case. Am I wrong to say that Maxwell's equations must hold in all inertial frames of reference? How would both Maxwell's equations be satisfied and the same results be obtained upon transformation to the second frame of reference?
Let's just ignore Maxwell's equations even. Here's another reason it seems inconsistent: What if we started our analysis in the second frame of reference instead, where $q$ is stationary? In this frame, we don't expect $q$ to move upwards. Then presumably, after transforming the $\textbf{E}$ and $\textbf{B}$ fields into the first reference frame, you should still see the same result (no upwards movement). So explaining the problem as "Lorentz transforms make $\textbf{B}$ into $\textbf{E}$" doesn't seem to cut it, you could just as well do the analysis backwards and get contradictory results.
Maybe you could argue that due to the ultimate symmetry of the field, there is no way to distinguish any movement of the charge so that it's meaningless to talk about this. This just feels like a cop-out to me. It would also seem to be easily evaded, since what if I just defined $\textbf{B}$ to be zero outside of $(-\infty,\infty)\times[-1,1]$? In this case, any upward movement of the charge would be noticeable, and we still have the same problem that we started with.
EDIT: Regarding the original source of $\textbf{B}$, let's just say that it's created by either a large solenoid or two permanent magnets so that $\textbf{B}$ is approximately uniform in the region of interest. A finite $\textbf{B}$ field like this will create induced $\textbf{E}$ fields at the fringes when it moves, but this shouldn't affect the local uniform region.