How our scrum team went from a blank page to a reasonable plan in a half day

Iterative development is a lot easier when you have something upon which to iterate.  Unfortunately, that isn't always the case. 

Pulling items from the backlog is one thing, but starting from scratch with a new development project has always given our team some difficulties.  The approach we took with our current project isn't revolutionary -- it is really just a flavor of a release planning process.  But I was so pleased with how quickly it came together (in roughly 4 hours from a blank whiteboard to a release plan, an almost fully planned sprint, and a prioritized backlog), I thought I'd share.  

The steps we followed:

1. Based on what we had on hand--an existing site we were migrating/uplifting, several discussions with the clients, some initial feedback from a user survey we'd done for users of the current site--we white-boarded the epic-level bodies of work for the new development. These varied widely by the size of the effort required to deliver them.
2. Once we'd exhausted our knowledge and thought we had all the "cards" required to deliver the project, we put them all in a Google Spreadsheet along the top row.  
3. Then, collectively, we all went into the spreadsheet and filled in (under each feature or other body of work) what user stories we could immediately conceive as required to deliver that feature/function.  Some of these were spikes or proof-of-concept user stories that would inevitably lead to other stories, but we filled in all we could imagine it would take to deliver that body of work.
4. This process led to a lot of discussion about each feature as we looked over our stories and those of our teammates. This discussion took most of the time we spent together.  It took very little time to populate a large number of user stories in this live, collaborative  approach. We prompted each other to expand on ideas or create new stories we hadn't considered solely on our own.  Also, because we worked on multiple features simultaneously, there was a synergy that came from considering multiple facets of the system at once and how they might interact.
5. Having all the stories in front of us, we talked with the product owner and defined a set of staged deliveries of the project, framing up four releases until a minimum viable product could be released to the client. We understood this could change as we develop the project, but it was a conceptual starting point we could revisit after the first release.
6. Then, we didn't try to put every user story into a release, though the release for some of them was implied.  We simply shaded all of the user stories that weren't going to be in the initial release in one color, and shaded those we needed to meet the product owner's initial release in a different color.  The ones that weren't ready to go will make up our backlog and are being captured in our tracking tool (we use Rally). 
7. We then worked to decompose those initial release user stories to make sure they were sized appropriately for the sprint(s), did planning poker, and copied them into Rally with our definition of done and placeholders for acceptance criteria (which we'll fill in tomorrow).

What made this seem productive and fast?

I think the key steps were taking our time in step #1, which helped us really get our arms around scope, then working simultaneously and collaboratively in steps #3-4, which helped us get a lot of user stories defined in a very short period of time.  

We'll learn in time--with demos and stakeholder feedback, releases and retrospectives, if our approach put us in a good starting point for success or if it let us overlook key project needs.  But out of the gate, it felt very productive and the team feels positive about the work ahead.