yeah but i understand why they changed it. it's true that jedis shouldn't think about revenge (well, as far as i know, haven't met a jedi yet so couldn't ask that question...). and in the movie there is actually no revenge, so the title would have been misleading. birth of the empire sounds cool to me...but you can't really have a worse title than "the phantom menace"...gah!
gundark's suggestions are very good as well, you should try to contact GL about them...