I found an answer to my own question...
I needed to specify the Latex interpreter as an option in the legend function, rather than in the later lines - see updated code below. It used to be the opposite due to a bug in previous versions (link to bug report). The bug fix may be causing the issue with exporting.
Hopefully this answer helps somebody else.
% Plot data
x = linspace(0,2*pi);
figure
plot(x,sin(x),x,cos(x))
% Create legend with Latex syntax
[hl,ho] = legend('$10^4$','6\,($10^5$)','Orientation','Horizontal','Interpreter','Latex');
set(hl,'box','off','Location','SouthWest')
% Adjust legend label #1
%ho(1).Interpreter = 'Latex';
ho(1).Position(1) = ho(1).Position(1)-0.1;
ho(3).XData(2) = ho(3).XData(2)-0.1;
% Adjust legend label #2
%ho(2).Interpreter = 'Latex';
ho(2).Position(1) = ho(2).Position(1)-0.3;
ho(5).XData(1) = ho(5).XData(1)-0.2;
ho(5).XData(2) = ho(5).XData(2)-0.3;
% Export figure
saveas(gcf,'test','epsc')

