Valor
Fatality.
Slow-as-hell battle system (SNES/PSX was much faster), crappy translation (Cress? Claus?), graphics downgrades, story is generally dumbed down for the E-10 crowd, and they removed: Lilith, the S.D., Satsugeki Bukouken, Odin, Shadow's dungeon, Groovy Arche, the face chats (think skits), and the nice new map graphics. Among other things, I guess.
Wait, Lilith? Isn't that Tales of Destiny? Groovy Arche is still in, I believe. I don't think the skits would have been able to make it on the GBA. And the SD faces were really ugly.
My only complaint about the translation was the change in Dhaos. Rather than being perhaps the most serious character ever in a Tales game, he's been made less evil. Any other complaint has to do with the GBA's pathetic capabilities. They used the SNES map walking and opening scene, yet used less-detailed PSX sprites.
Wonder what would have happened if they worked on the Full-Voice Edition on the PSP instead...