You need to save the handles to the line objects (i.e. the output of plot) in an array. Then you can re-order that array as you please. If you use the 'DisplayName' option in plot, you can avoid having to re-order a cell with the names as well.
%example:
h=[];%make sure h is empty
h(1)=plot(1:5,5+rand(1,5),'rd-','DisplayName','A');
hold on
h(2)=plot(1:5,7+rand(1,5),'bd-','DisplayName','B');
%re-order
order=[2 1];
h=h(order);
legend(h)
Another method is just to re-order the legend once you have it:
h = gca;
hC = findobj(h,'Type','line');
order=[2 1];
legend(hC(order));
