This is a consequence of a theorem from classical mechanics.
The magnetic force is non conservative and so it is not suitable for the standard approach to the Lagrange formalism. 

The form that the Lagrange equations normally take is:
$$ {d \over dt} { \partial L \over d \dot q_i} -{ \partial L \over d q_i}=0$$ 
This only holds for conservative Systems (Potentials not dependent on speed). But for Potentials $U(q_1,...,\dot q_1,...,t)$  depending on speed that can be arranged in a special form there is an exception. That is, only if they can be arranged so that the force they represent can be rewritten as:
$$F_j={d \over dt} { \partial U \over d \dot q_j}-{ \partial U \over d q_i} $$

Luckily for us this is the case for the electromagnetic force, the potential of the form:
$$U= q(\Phi - \dot x \vec A)$$fulfills the requirement above.

But your question was why this is. If you Only demand independent coordinates, and not conservative Potentials, the d'Alambert priciple which is equivalent, to the Lagrange equation takes the Form: $$F_j={d \over dt}{ \partial T \over d \dot q_j}-{ \partial T \over d q_i}$$
where T is the kinetic Energy and $F_j$ a generalized force.

It is obvious that if you can write the force in the form given above we get back to the good old Lagrange equation with $L=T-U$.