One of the key foundations and most attractive principle of Agile or Lean methodologies is that "Everyone can help each other remain focused on the highest possible business value per unit of time".
I am certainly a strong supporter of that principle. However, value is often difficult to assess, I would actually argue that it is easier to identify what has less or little value, but what we think as valuable can potentially lead to many false positive, or simply be "business-as-usual" and hide the broader structure of the solution.
"User Stories" are the corner stone of identifying and delivering value:
An argument can be made that the user story is the most important artifact in agile development, because it is the container that primarily carries the value stream to the user, and agile development is all about rapid value delivery.
In practice, very few people focus on the benefits part of a user story. All user stories I see are either what we used to call "requirements" (just phrased slightly differently but isomorphically) or "tasks" needed to advance the state of the project.
However, there is a fundamental flaw in the construction of user stories, even when they are properly written, because they somehow make an assumption about the shape of the solution, and drive the author to turn almost immediately in solution mode, leaving no room for creative and out-of-the-box thinking.
Let's compare the metamodel of a User Story and to the formal definition of a Problem. The metamodel of a User Story looks like that (using the BOLT notation):
As a <role> I want to <action> so that <benefit>
I define a problem formally as a non existing transition between two known states , the metamodel of a problem looks like that:
A solution is a way to transition between these two states. Please note that both the actors and the actions are part of the solution:
This is where the problem lies when using User Stories, you are specifying the requirements with the solution in mind. There is, of course, a general relationship between some of the actors and entities of the system with the "start" and "end" states of the problem. The problem states are always defined in terms of their respective states (possibly as a composite state), but it is a mistake to think that the actors and entities that perform the actions, as part of the solution, are always the same as the actors and entities related to the (problem) states.
Hence, an action is solution centric and should not be part of the problem definition. As soon as you pick one, you have put a stake in the ground towards the direction you are going to take to solve the underlying problem. The other issue is that the start and end states are never clearly identified in a user story leading to confusion in the in the solutioning and verification process, since the problem is not defined with enough precision. Benefits could sometimes align with the target/desirable state, but the definition is often too fluffy and more goal centric, not effectively representing that (problem) state.
Ultimately, the relationship between problems and solutions is a graph (states, transitions as problems, actions as solutions), and this is where the coupling between the problem space and the solution space at the User Story level becomes unfortunate. This means that User stories cannot be effectively nested and clearly cannot fit in hierarchical structures (which is common to most Agile tools I know). This problem is quite accute as teams struggle to connect business level user stories and system level or solution level user stories. The concept of having a single parent directly conflicts with the possibility of having multiple possible transitions into a single state and decomposition principles where the same problem appears in the decomposition of several higher level problems.
I feel that distinction is profound because we can now clearly articulate:
a) the problem statements with respect to each other (as a graph of states and transitions)
b) we can articulate the solution in relation to the problem statements
c) we can articulate the verification (BDD) in relation to the problem and solution 
d) we can actually articulate the Business Strategy , the Problem Statement, the Solution and the Verification with the same conceptual framework
e) derive the Organizational IQ from the problems being solved on an every day basis
To the best of my knowledge none of these articulations have been suggested before and no one has ever provided a unified framework that spans such a broad conceptual view from the Business Strategy to the Verification. In the proposed framework the business strategy is simply a higher level and specialized view of the problem and solution domains, but using the exact same semantics (which are described here). In other words the enterprise is a solution to a problem, which is a composition of smaller problems and more fine grained solutions, etc. This has an extremely important implication for the execution of the strategy because now both the Strategy and its Execution are perfectly aligned, at the semantic level: the strategy, problem, solution and verification graph represent a map that everyone in the organization can refer to.
To take advantage of this new conceptual framework. I suggest that we make a very simple and easy change to Agile and replace "user stories" by "problem statements". Each problem must be "solutioned", either by decomposing it into simpler problems or solutioning it directly. Value can still be used to prioritize which problems are addressed first, that part of the Agile and Lean movement is very valuable, so too speak, but the focus on problems and solutions opens a new flexibility in how we handle the long range aspects of the solution while enabling the highest level of creativity and ultimately a direct articulation with the IQ of the organization.
As problems are decomposed, we will eventually reach a point where the subproblems will be close to or isomorphically related to the solution. But it would be a mistake to not clearly delineate the problems from solutions, simply because at the lowest level, they appear isomorphic.
The fact that the lifecycle is pretty much identical as the one of a user story enables most of the Agile processes and tools to work nearly unchanged.
You may want to know "How do I write a Problem Statement?". Personally, I don't like canned approaches. Oviously here, the mere definition of the two states (low value and high value) is enough to describe the problem. If a solution already exists (i.e. it is possible to transition between these two states) you may want to describe some characteristics of the new solution. I googled "How to write a Problem Statement?" and I felt there was already a good alignment betweent the results and the abstract definition provided above. For instance:
We want all of our software releases to go to production seamlessly, without defects, where everyone is aware and informed of the outcomes and status. (Vision)
Today we have too many release failures that result in too many rollback failures. If we ignore this problem; resources will need to increase to handle the cascading problems, and we may miss critical customer deadlines which could result in lost revenue, SLA penalties, lost business, and further damage to our quality reputation. (Issue Statement)
Here we see two states for the releases: initial state (low value) tested, and the high value state (in production). There is also an undesirable state (failure) that the new solution will prevent reaching. For me the most important thing is that the problem statement must avoid at all cost to refer to the solution. Even if the people specifying the problem statement have an idea about the solution, they should capture it separately.
This new focus on problem & solution provides a rich conceptual framework to effectively organize the work of a team. After all, we have been innovating, i.e. creating solutions to problems, for thousands of years, so it is no surprise that our vocabulary is quite rich. Here are a few concepts that could be used:
Goal: a goal is not a problem, but you often need to solve problems to reach goals, so it's important to keep them in mind
Fact: a fact often constrains the solution, so they need to be clearly surfaced and accounted for
Assumption: assumptions are very important because they also constrain the solution, but in a more flexible way. Assumptions can be changed, facts generally cannot.
Statement: the problem statement is what physically replaces the user story.
Hurdle: During the decomposition of a problem, hurdles might be identified, they are not a problem per say, but they impact the solution. It could be for instance that a resource is not available in time to meet the deadline.
Snag: A problem can be downgraded to a snag as the solution is obvious to the team and represent a low level of effort. It can also be a small unexpected issue, that need to be quickly resolved.
Dilemma: A problem can be upgraded to a dilemma, when several solutions are possible and it is not clear which one to chose
Setback: The team can suffer a setback when it thought it had found the solution but it didn't, or could not find a solution and need to reassess either the problem or the approach
On the solution side, we can also capture different elements and stages of the solutioning process:
Answer: Findings related to a question raised in the problem statement.
Result: A validation that the solution conforms to a Fact
Resolution: The choice made after reaching a dilemma
Fix: a temporary solution to a problem or a snag to make progress towards the solution to the greater problem
Development: An element of the solution, usually the solution to a subproblem or a snag
Breakthrough: The solution found after reaching a setback
Way out: A solution was not found, nevertheless, the project reached a satisfactory state to meet some or all of the initial goals
From a management perspective. The Solution or Delivery Manager can escape the bureaucracy that Agile has created. Ironically, moving stickers around is a zero value activity, with zero impact on the organizational IQ. The solution manager can and should be responsible for the IQ of the project, which rolls up and benefits from the IQ of the organization. It should keep track of the elements that are incorporated in the solution as problems are solved. It should encourage team members to be creative when necessary and to shamelessly adopt existing solutions when it makes sense. It should help resolve dilemmas and push for breakthroughs.
The PMO organization becomes the steward of the Organization's IQ.
As we define problems and solutions in terms of entities, state, transitions and actions, the BOLT methodology provides a unified conceptual framework that spans from Business Strategy to Problem and Solution Domains to Verification (BDD).
1) We have provided a formal model of a problem and a solution, and how they relate to each other
2) This formal model offers the ability to compose problems and solutions at any scale, over the scope of the enterprise
3) Problems and Solutions can be composed from Business Strategy down to Verification
4) We suggest that Agile methodologies replace User Stories by Problem Statements
5) With the renewed focus on "problems", we can also integrate the work of Prof. Knott on Organizational IQ in the whole framework
Last, but not least, decoupling problem definition and solution yields a tremendous benefit in the sense that both can evolve independently during the construction process.
 For instance, you build a vehicle, obviously you want to car to transition to the "in motion" state. Different "actions" will lead to the vehicle to reach that state (a horse pulling, an engine, transmission and wheels, a fan, ...).
 BDD Metamodel (Scenario):
 Living Social Business Strategy mapped using the same conceptual framework (Source: B = mc2)
TLDR: Add more detail to use stories
Thank you Mike, I have disabled the spam filtering and re-posted your comment as-is. Apologies for that.
I have been working in some teams where User Stories are treated more like traditional requirements, especially as you cross the boundary from “business level requirements” to “system level requirements” and architecture. This is especially true of distributed teams where it is very difficult to have open discussions and you focus mostly on the communication from one team to another (following Conway’s Law).
The biggest impediments I have experienced (and addressed using Problem Statements) are:
- Most product owners jump in solution mode without any a priory discussion and clarification of the problem, sometimes going as far as dictating the architecture
- When you deal with existing functionality, it is tempting to just specify how different you want it to be, rather clearly expressing the problem you are trying to solve
- The hierarchical nature of tools that manage User Stories make it nearly impossible to manage large back-logs.
- Since the User Stories are the only visible items during the delivery process, it is difficult to create an efficient verification process