Online multiplayer is complete! It actually didn't take much time to implement the gameplay changes. In order to get a full featured lobby I already had to wrap my mind around multiplayer, rewrite portions of the game to support 8 players, and implement both peer to peer and client server communication. By the time I started hooking muliplayer communication into the gameplay code I discovered that I had already done most of the work.
The conventional wisdom among developers is that online multiplayer is extremely difficult. Perhaps it is. But if you've already completed a game and learned how to do animation, storage and local multiplayer, you probably won't find it more difficult than other challenges you've already tackled.
In total, it took about 4 weeks to learn how to do online multiplayer and add it to my existing local multiplayer game. I couldn't have done it without Microsoft's code samples and Shawn's well written blog post explaining when to use client server and peer to peer. It should now be quite easy to include online multiplayer in my future titles.