The place where the last battle takes place is new, the Damaged Flying Tower. That wasn't on the NES version.
The last boss is new too, well not really new.
Where the game was supossed to end on the NES version (fight with the computer Dyna) it continues on the GBC giving you the Crystalis Sword and sending you to the Damaged Flying Tower maze, with a last fight with Draygon. Draygon is nothing more than a more powerful version of Dragonia, the boss you fought on the pyramid level.
*EDIT* I found some sites with info and differences:
tpb68.tripod.com/differences.htmlwww.toastyfrog.com/toastywiki/index.php/Site/Crystalisen.wikipedia.org/wiki/CrystalisAnd differences from a FAQ at Gamefaqs:
1. The storyline has changed a whole lot through the game. Think
back to how the story went on the NES version, and you'll know
what I'm talking about. Not only that, the music has changed, for
the worst, I might add.
2. The GBC Cave, or Gameboy Color Cave. I call it this, because
it's a new cave that can only be accessed on the GBC version,
hence the name. It's a small cave, that has the Alarm Flute in it.
3. When you get either a Ball or Bracelet for a sword, they have
an attack rating as well, which will increase your sword power.
4. Alot of the enemies have change, like the Killer Chest isn't as
popular as it once was. Not only that, it seems any sword can kill
any enemy atleast from what I can see.
5. There is a couple new items, well new in the sense that they
wasn't in the NES version, but they are simple. The Necklace Of
Fate and Kensu's Body (don't ask). Deo's Pendant (NES version) was
changed to Stom's Pendant, but it works the same as Deo's Pendant.
6. Some of the names of locations have changed (Evil Spirit Island
is now Island of Spirits for example). Also some of the story has
changed from the NES version, but it's generally the same story.
7. Probably the big kicker, you have to defeat DYNA BEFORE
fighting the final form of Dragonia. Here's another strange bit,
you don't get the Sword Of Crystalis till after defeating DYNA,
which you will use it on Dragonia's final form.
8. The Flying Tower (Floating Tower) went through a huge
changeover, making it a bit more difficult to get through.