What did you update from?
At some point calibre was changed to use title sorting when sending books to the device. I don't recall when that happened, but it was in the last few versions. It might be that you are seeing the effects of this change. Hard to know from your description.
At that time a 'tweak' was added to change this behavior. The tweak documentation is:
Code:
# Control how title and series names are formatted when saving to disk/sending
# to device. If set to library_order, leading articles such as The and A will
# be put at the end
# If set to 'strictly_alphabetic', the titles will be sorted without processing
# For example, with library_order, "The Client" will become "Client, The". With
# strictly_alphabetic, it would remain "The Client".
save_template_title_series_sorting = 'library_order'
Change tweaks by going to preferences -> advanced -> tweaks.