The ncx dbt:uid entry being flagged if it doesn't match the opf unique-id is actually relatively new to Epubcheck. I'm almost certain it wasn't problem back in 2013.
In all honesty, I wouldn't even bother removing the uuid, or changing the unique-id from the uuid to the new isbn entry. It's really not worth the trouble, and there's absolutely no advantage to be gained. Just leave the uuid, the unique-id, and the ncx dbt:uid alone; then add a new ISBN meta item and be done with it.
I can't remember the last commercial epub I looked at that used the isbn as the unique identifier. *shrug*