During our latest project (currently put on hold, grrr...) we started to plan using UserStories. The problem was that we were designing a 'language'; in this case a modeling language that allows a developer to model a UI instead of programming out all the event handlers. We had a number of requirements that were fairly vague: there must be support for handling exceptional situations, there must be support for menu's, etc. Now we had two options: (1) complete the specification of our language first, and then write UserStories and implement; or (2) don't write UserStories yet for the vague areas, and start to implement what is known already. We chose for option (2). The reason is that we only could see how to fill in the vague areas once we had something running, something that our poor alpha-users could shoot at and comment on. BUT for the planning we couldn't simply ignore the vague requirements. That's when we introduced the concept of a story idea.
A story idea is a description (a paragraph of text, usually) that has to be turned into user stories before it can be implemented. Just as a user story, an estimate is made for the effort needed to implement it. But here we cannot do some design work before planning -- we have to take a rough shot. But a rough estimate is better than nothing. The time estimate also included the time needed for 'research' and for writing up and discussing the user-stories-to-be.
Just like user stories, we also had priorities on story ideas. And we scheduled the 'story idea -> user stories' conversion in as separate tasks for the relevant team members.
(By the way, it seems to me that story ideas are more needed when using XpForLanguages or XpForProducts then for XpForSolutions.)
Opinions?