Usualy I prefer games where everything has an explanation as to where it comes from and why its there which is why I find it frustrating that there is no explanation or story to minecraft.

This is why I think that Notch should introduce a new gamemode that allows you to play how you normaly would in survival but instead of trying to destroy an enderdragon for no reason, you have a fully developed storyline/adventure to follow.

This allows for answers to many questions that I personaly have always wanted to be answered such as:

• Who built the abandoned mineshafts?
  
• Who built the dungeons?
  
• Who built the nether fortresses?
  
• Who built the strongholds?
  
• Why are there endportals in the strongholds?
  
• Why are there human skeletons and zombies but you are the only living human?
  
• Why are there pigzombies but no pigmen?
  
• What is the end dimension?
  
• What happened to the other humans?
  

For the storyline to make sense the characters original spawning has to make sense so I think the player should start by waking up on a stone bed in a stronghold like chamber underground with a single passage leading to the surface. However I haven't been able to think of a way to prevent players from using the chamber as a home or mining its blocks as a resource early on giving them an early advantage. The only possible solutions to this I can think of is to cave in the passage when you leave however it could still be excavated, build it out of a new unbreakable block but it could still be lived in, simply dissapear and be replaced by naturaly generated terrain with the spawn point being relocated to your current position or to explode as you leave leaving nothing but a crater.

After your original spawn the objective would be to play as normal until you find an abandoned mineshaft or dungeon where you would then realise there were once other people and you start your quest to find out what happened to them. On the way you will find clues and journals that hint towards what caused humans to vanish and pigmen to become zombies. at the end of your journey you are confronted with a portal, much bigger than any of the others and when you step through it the credits role. This inconclusive ending leaves infinite space for extension and a cliffhanger for additional sections to be added as a part of updates.