Beautiful graphs - love it!
It should be stable with a 30 deg margin, so I suspect there is some more phase shift somewhere. Not sure how you did your measurements, but did it take into account the phase shift caused by the filter cap on the rectified output? If it did, no load will be the worse case scenario, and full load will be the most stable scenario.
Some switching regulators need a minimum load for just this reason, but I do not like that as a solution. What is the oscillation frequency of the instability? Was t 28KHz? Can't quite read the graph. You could try adding some lead compensation in the voltage divider to the regulator - like a cap in parallel to the top resistor in the divider.
What you normally want to see is a 6db/octave roll-off in the loop gain above the zero gain point - much more then that and you will almost certainly have stability issues to deal with. It looks like that even with compensation, you are getting more like a 12db/octave roll-off between 10kH and 20kHz. See what some lead compensation at 15Khz does.