Here, there are some themes:
For Castle, maybe a mythical story: The Legend of King Arthur and the Knights of the Rounded Table (but, that sounds like Lego Classic Castle, isn't?)
Also, I think Lego can mix elements like Castle 2007 and others from the Warcraft Series or The Lord of the Rings for do its own story, without purchasing a lIcense (the sets will increment their cost considerably). Griffins, Dragons, Trolls, Ogres, Humans, Pegasus, Unicorns, Elves, Centaurs, Skeletons, Knights mounted mythical beasts. All that is good for children and AFOLs. Also, maybe each faction has its own unique power (elves has archers and druids manipulates nature energy so well, humans use force and a little magic, undead spread terror, etc.). Even a RPG can be played with this.
For Lego City, maybe a "Fast and Furious" subtheme, or a SWAT subtheme, because Agents was too short.
Space-Fiction/Exoforce like: combining Gundam, Exoforce and the best ideas from Lego Star Wars, for make a Lego Unique theme. Story tells about the last human colony traveling in the space finding a planet like the Earth, because it was invaded by a alien race that it's gathering resources for expand its domain and confront their real enemy (another alien race). Humans has many troubles, because they are persecuted by the alien races and sometimes humans will be in a crossfire from a fight originated by the alien races. Humans have a mothership and a lot of robots, combat aircrafts, battlepods, armors, etc. Aliens has superior technology and weapons. Can human race find a Planet where they can live in peace?
- "If you know the Formula, apply it"