*ahem* More like Namco's American office changed the names from the originals. Proof as follows. These are pictures of the main characters' names from the official guide book of the very first incarnation of Tales of Phantasia (the SFC version). While some people may argue things like translating katakana (Japanese characters used for English and other foreign words) can be very arbitrary sometimes, and kuresu (romaji'd version of Cless' Japanese name) technically would be Cress, not Cless... well, the problem with that is the guide book has the names IN ENGLISH as well. Behold! (sorry for the crappy quality, but I'd rather not break the bind of my copy of this book to scan the pics in, so you get crappy cellphone pics instead)
You have to have entered Dhaos' castle (the last one, yes) first. After doing so you can leave and do those two sidequests. This is why I have you leave right after completing the first two floors of the castle (i.e., here).
See the answer for the first question. Go here for what to do for the beginning parts of that castle.
