There are a few suggestions that I can think of:
1) The time limit of 30/60 seconds is good, but not perfect. Due to the ever changing nature of battle, a creature that is summoned next to a spellcaster can force that character to completely change his decision for his action. In other words, don't try to stick to this too rigidly.
2) In order to help keep PCs focused on major tasks and major NPCs, we should be given a list of major NPCs to keep at the table for our session. Basically, this should just be a list of names with lots of space for us to write what he have already learned about these NPCs under their names. As we learn more, we can update these sheets (which are shared by all players). This will prevent people from continually asking the DM and other players to repeat what was said to them by a certain NPC. Although, perhaps starting this mid-campaign, it might be good if we just got a bit of information, similar to what is already in the character's description in the player's guide. If someone is not paying attention, they can read the update on the NPC sheet after. As well, it will help us focus on who the major NPCs really are without getting bogged down in secondary characters that add flavor more then story. Similarly, a "To Do" sheet can be equally helpful.
3) Email should be the major form of correspondence when working out individual character's side stories. As well, we should be limited in how much time we have to work out these plots. After every 1 or 2 adventures, we should have 1 session that is devoted to selling and buying loot, resolving character plots that people have been communicating with the DM about online and figuring out where to go next. The key is to limit this to 1 session. Anything that doesn't get done in that session can be done in the next "down time" session or by email. We need limits, otherwise we will go overboard with irrelevant individual plots.
4) This brings me to the last suggestion (for the moment), which is that each player should limit how much they try to do with their character. It may be fun to have all the other players and the DM (and thus the NPCs of the setting) cater to your character for several hours of game time, but it can be somewhat selfish and reduce enjoyment for other characters. Now, to be explicit, I do think that each character should have 1 or 2 side stories going on, mostly from their background or spinning off of plot events in the campaign, because without these our characters become sterile and generic. It is the players' responsibilities to limit themselves to plots that are relevant and preferably involve other players as well. Our group tends to prefer a balance between "role-playing" and "roll-playing", so if one character spends too much time with own mostly irrelevant side story the has little to do with other players, our group does not generally appreciate this. Basically, all I'm trying to say is that the slow down that our game is suffering is both a problem caused by the players who want (and force) their characters to be the "stars" as it is by the fact that we are getting higher level and more options are appearing for us.