Well, 'real creativity' is a tough thing to pin down or talk about at the best of times. I think it can be achieved with conventional computing, but I think many people would reject it as creative even when faced with it.
As you say, though, creative or not I'm just happy to be producing software that can make fun(-ish) games!
Fitness is easily the trickiest part of both projects so far. We're using co-operative co-evolution so elements of the game design are evaluated separately as well as together. For the Metroidvania, the key bit of the FF is "the play should have to collect all the powerups, in a mostly total order, to reach the exit". What this does is create segmented levels that have 'stages' which you access through powerup collection.
For the arcade games it was a lot more general. We did a lot of very rough heuristics like "maps shouldn't be too cluttered", "you should have to explore most of the screen to win" and things like that. I want to go back to arcade games becuase it's a much harder problem to design games without genre staples.
Evolution is a pretty cool tool. That said, it has its limitations! Inventing brand new mechanics seems to be a particularly tricky problem, for instance. Look at something as left-field as Antichamber (from this year's IGF). That takes some creativity to come up with, I think.
Still, that's why it's research! Wouldn't be fun without feeling a bit impossible.
Hey, I'm the guy behind ANGELINA - glad you like the project! The New Scientist game is available to play on that link, near the bottom of the article. You can also check out older games (less impressive than the one we made for NS!) over on the project site: www.gamesbyangelina.org/games