Does it matter what type of file you export the graph as?
Well, in OpenOffice, pdf is the only option. And Excel doesn't have a specific "export" option.
But I've actually just gone back to Excel and tried saving as a pdf, and that also works - and without screwing up the text, so it's even better. I could have sworn that I tried that, but I must have only tried printing to pdf.
So apparently my problem wasn't so difficult after all, although I still think it was a very irritating change to have made to Excel.
Anyway, thanks for the suggestions!