The answer of Luboš Motl is of some help, in that it shows how to bring in the sorts of insights which relativity offers, but nevertheless it opens with its overall conclusion, and that conclusion is wrong. It is wrong largely for the reasons briefly indicated in the answer of WIMP.
The question is important, and it is important to get the answer right. The question is:
Can Maxwell's equations be derived using only Coulomb's Law and Special Relativity?
The answer is: no, because plenty of other field theories that respect Special Relativity can be invented, such that they reproduce Coulomb's Law in the rest frame of a point charge in inertial (i.e. non-accelerated) motion.
However, what one can say, is that classical electromagnetism (i.e. Maxwell's equation and the Lorentz force equation, or any formulation equivalent to this, such as a Lagrangian formulation) is among the simplest field theories that respect Special Relativity and include Coulomb's law. The definition of 'simplest' here is admittedly imprecise.
The main reason why you can't derive Maxwell from 'Coulomb + S.R.' is that you would not know whether to include acceleration effects in the relationship between potentials and charges.
Now I will 'lift the lid' a little on the theoretical physics here. A very good (not the only) mathematical way to ensure that any piece of physics respects Special Relativity (S.R.) is to restrict oneself to tensorial expressions in everything you propose and write down. Here 'tensorial' includes tensors of rank zero, i.e. scalars, but not just any old scalars: they would be Lorentz-invariant scalars. It also includes 4-vectors and second- and higher- rank tensors. When taking derivatives, you use the covariant gradient operator $\partial_a$, and then you have a tool kit for constructing differential equations that respect S.R.
So the 'simplest' field theory might be one such that particles can have a Lorentz-invariant scalar property called charge $q$, and the force on a charged particle is independent of the 4-velocity $u^a$ of the particle. The trouble is that you quickly find that in such a theory the force on a particle cannot change the velocity of a particle without also changing its mass. Exploring further, you try allowing the 4-force $f^a$ to be dependent on the 4-velocity through a simple linear equation involving a scalar field $\phi$, such as $f^a = q \phi u^q$ (?). Still no good (mass changes again). So you are led to try a second-rank tensor $F^{ab}$ for the field, because it is the simplest thing, other than a scalar, which can take a 4-vector $u^a$ as input and give back a 4-vector force:
$f^a = q F^{a\mu} u_\mu$
Now it's ok: the force is mass-preserving as long as $F^{ab}$ is antisymmetric. Good! An antisymmetric tensor is the simplest type of second-rank tensor. Next we want a differential equation for this field: try the simplest thing, which is to take the divergence, and you are well on the way to Maxwell's equations. If we now bring in Coulomb's law (and this is where it comes in), then you are guaranteed to get two of Maxwell's equations if you restrict the source term in your differential equation to only a single term proportional to charge density and 4-velocity. Coulomb's law does not itself tell you not to add in further terms to do with 4-acceleration.
By this approach we do not arrive inexorably at Maxwell's equations, but one does find that they are arguably the simplest that include the property of charge conservation and that allow a mass-preserving force (in technical language, a pure force).
Among other field theories that one encounters there is one that is much like Maxwell but includes magnetic monopoles. This arises very naturally, in the theoretical treatment, and is certainly a serious candidate possibility for how the physical world really works. It is somewhat less simple in that one loses the nice property of writing the field tensor as a 4-curl of a 4-vector field (the 4-potential), and the theory no longer respects symmetry under space inversion (parity). See Jackson's book on electromagnetism for a discussion. If there are in fact magnetic monopoles, as many versions of quantum field theory suggest, then the puzzle is why electric monopoles are so much more abundant than magnetic monopoles.
However, I would like to underline that this magnetic monopole issue is far from the only reason Maxwell's equations are not fully derivable from Coulomb's law and S.R. The other reasons include that one can easily imagine that the field equations involve higher-order derivatives of the motion of the particle; S.R. on its own cannot tell you that they don't. By starting out with a Lagrangian approach, one can introduce further constraints, such as invariance leading to conservation laws, and then electromagnetism is quite tightly, but still not fully, constrained. Fundamentally, what S.R. can tell you is that a field which provides a force independent of a body's velocity cannot be the whole story about the physics. Such a field (such as the electric field) must be in partnership with further effects which do depend on a body's velocity.