Electric potential propagation speed We know, that the electric potential for some charge $Q$ is $\Phi=\frac{Q}{4\pi\epsilon|\vec{d}|}$ where $\vec{d}$ is the distance between the point where we measure the potential and the origin of the charge. 
Suppose we have some ball with charge $Q$ surrounded by a hull with charge $-Q$. Then this setup looks for some test charge $q$ being placed far away like there was no charge at all. Now if we remove the hull, the test charge 'sees' a potential $\Phi$ and therefrom experiences a force $F=-q\vec{\nabla}\Phi$.
If my understanding is correct, then as a consequence of Einstein's theory of special relativity the test charge $q$ does not move instantly. Instead it takes some time until the potential change got propagated the distance $\vec{d}$ and hence it takes some time until the test charge experiences the force from the newly created potential.
Is this non-instantaneous propagation of the electric potential (and of the magnetic vector potential) encoded in Maxwell's theory or does his electromagnetics assume an instant change of the four-potential everywhere?
 A: The answer depends somewhat on which choice in gauge you use.  If you choose the Coulomb gauge, then the scalar potential obeys the Poisson equation 
$$\nabla^2 \phi = -\rho/\epsilon_0$$
while the vector potential obeys the wave equation 
$$\left(\nabla^2 - \frac{1}{c^2}\frac{\partial^2}{\partial t^2}\right)\vec A = -\mu_0 \vec J + \frac{1}{c^2}\nabla \left(\frac{\partial \phi}{\partial t}\right)$$
In this case, there turns out to be an instantaneous change in both potentials, but they compensate for each other in such a way that the electromagnetic field at some point $\vec x$ relative to the source remains unchanged until a time $t=|\vec x|/c$.
On the other hand, if you choose the Lorenz gauge, then both the scalar and vector potentials satisfy the wave equation
$$\left(\nabla^2 - \frac{1}{c^2}\frac{\partial^2}{\partial t^2}\right)\phi = -\rho/\epsilon_0$$
$$\left(\nabla^2 - \frac{1}{c^2}\frac{\partial^2}{\partial t^2}\right)\vec A = -\mu_0 \vec J $$
In this case, changes in both potentials propagate outward at the speed of light.
A: Maxwell's equation are, unlike Newtonian mechanics, not Galilei-invariant but Lorentz-invariant - so they are actually exhibiting the same symmetry as 'pure' special relativity. The speed of light is therefore inherently included in Maxwell's equations as the limiting speed of propagation by the equation's symmetry.
Therefore, yes, classical electrodynamics will for moving charges also predict electromagnetic fields that spread with a certain velocity and do not appear instanteneously.
For more on this matter, I'd suggest you e.g. the classic treatise by J. D. Jackson: Classical Electrodynamics (Wiley New York, 1999).
