On import of an Excel spreadsheet, labels do not get added to new stories.
If you export stories to Excel and add labels to them, you can then re-import them and the labels get added.
So: Import / Export / Import
This answers the very problem with my story import I was trying to fix.
Thanks,