It may be the find part of your find-replace that is wrong.
In the Find what: section, use Format and select Font.
In the Font dialog in the Underline section try Underline Words Only, or if you used that, try another underline style.
The font, font style and font size boxes are left empty.
Do not have any characters in either the Find or the Replace boxes.
In Replace with, select Format and Font
Select Font style Italic and Underline - None.
Font name and size are left empty.
This worked on a sample document, replacing underlined text with italic font - but what was replaced depended on how it was underlined!