Disclaimer: If you really want to learn in-depth, insightful thoughts on gameplay progression, you should read Lopez' article on Gamasutra, instead. Myself, I´m just reporting a (not so meaningful) case in which the game's backstory is changed due to early gameplay issues.
If you´ve seen the screenshot I´ve submitted weeks ago, you probably know the game I´m working on is about maintaining flowers. The initial plan (and backstory) was to give the player a completely empty terrain, so he could start his garden from scratch. That, I thought, would emphasize the player´s freedom.
However, given the game´s pace on early tests, we´re thinking of starting the game with a single specimen already planted. Reasons for that include (a) giving something the player can care about right from the beginning, not being subject to (b) a long period of time without any flowers around.
As result, the storyline would have to change from something like "start a garden from scratch and create the flora of..." to something like "save the last flower and recreate the flora of...". Personally, I think players would be more captivated by the second line.