The circuit might not behave in a linear way during the transition, so loop gain theory (which assumes a linear circuit) might not be applicable during this time. This could be an explanation for an overshoot that is higher than predicted by the value of the phase margin.
A phase margin of 60 degrees should be adequate in most cases, 76 degrees are required to have no overshoot of the step response in a second-order system, see for example
http://powerelectronics.com/power_systems/simulation_modeling/Transient-response....