<< They say at B&N you should remove content (backup please!) with Non-ASCII-titles, eject nook, check for new content, reload content and the titles would be OK. >>
It turns out the fix was easier than that. After I posted, I walked in a B&N store. I fiddled with the WiFi, turning off then on again. After I did that, the titles were correct. I'm not exactly sure what I did that changed it.