Examples where momentum is not equal to $mv$? I am aware that momentum is the thing which is conserved due to symmetries in space (rotational symmetry, translaitonal symmetry, etc). I am aware that in some systems, the generalized momentum, 
$$p_j = {\partial \mathcal{L} \over \partial \dot{q}_j}$$
is not simply $mv$. One example of this might be a charged particle in an electric field, 
$$p_j = mv_i + {q \over c} A_i$$
Can anyone provide other examples where this is the case (simple, preferabily) and an intuition perhaps of why the "old" definition of momentum breaks down?
 A: the momentum is the quantity that is conserved as a result of the symmetry with respect to translations. This is the so-called Emmy Noether's theorem.
The only reason why we had $p=mv$ in classical mechanics was that the Lagrangian only depended on $\dot q$ by the kinetic energy $m\dot q^2/2$ term. By the differentiation, you may see that $p=m\dot q$. However, whenever the Lagrangian is different, the relationship between momentum and velocity gets modified. 
You quoted one example. Another example is any theory in relativity where
$$ p = \frac{m_0 v}{\sqrt{1-v^2/c^2}} $$
which may also be derived from the Lagrangian. Note that in the relativistic case, the Lagrangian is (minus) the proper time of the world line.
In some cases, the momentum gets modified but people have disagreed what it is. A recently discussed example here was the Abraham-Minkowski controversy about the momentum of a photon in a dielectric material:

Is the Abraham-Minkowski controversy resolved?

For photons, the momentum is $p=E/c$ in the vacuum - this itself is different from massive slow particles - but this relationship can get multiplied or divided by the index of refraction $n$, and arguments arose from this point.
In field theory, one has totally different formulae for the momentum. There are no particles i.e. no velocities of a few objects. Instead, the momentum is distributed in the field - e.g. electromagnetic field - and every region of space carries a momentum density. For example, the momentum density of the electromagnetic field is $\vec E\times \vec H$ or $\vec D\times \vec B$ - which of them is "true" was a famous controversy, equivalent to the controversy about the momentum of a single photon.
Other fields obviously have other formulae for the momentum density.
A: Generalized momentum and momentum are two separate things.
In an electromagnetic field, the mechanical (also known as the kinetic) momentum of a non-relativistic charged particle is still $\vec{p}=m\vec{v}$.
$\vec{P}=m\vec{v}+q\vec{A}$ is called the canonical momentum.
And in analytical mechanics, the generalized momentum can be almost everything, including position coordinates like $x,y,z$ or $r,\theta,\phi$.
A: Momentum defined as $mv$ isn't conserved in collisions approaching $c$, whereas relativistic momentum, $\gamma mv$, is. Hence the redefinition of momentum.
A: I think if you use non Cartesian coordinates in the expression $\mathbf{p}=m\mathbf{v}$, you will obtain something more generalized.
