"Don't come to me with problems"

I once approached a manager to discuss an issue that was weighing heavily on my mind and was told: "Don't come to me with problems, come to me with solutions!". The meeting quickly fizzled out, and I was left feeling demoralised.

I value my superior's time and only go to discuss a problem with them when:

I know that I don't know. Since the problem and possible solutions bleed beyond my sphere of responsibility, I want to discuss the issue with a superior. There may be information or context that I am not aware of which will influence possible solutions.
My solutions were not digestible. I have been in meetings where I have presented a problem and solutions but got feedback that I didn't offer any solutions. I chalk some of these to a communication failure on my part, but on other occasions, this was due to the solutions not being acceptable to the decision makers in the room.
I may need to kick the hornet's nest. I am concerned that my solutions will not be received well, so I present just the problem to try and get a sense of the mood or am laying the groundwork for further discussion.
I am stumped. I know this is a significant problem, and I have thought deeply about it, but my lack of experience/skills/context is preventing me from coming up with satisfying solutions. I am seeking mentoring/coaching so I can grow.

I talked to several friends in leadership positions about their thoughts and advice.

As a manager, some things to keep in mind:

Listen and acknowledge, that may be all you can do but may be all that is needed.
Once you understand the situation, provide more context/coaching so they can go and develop some great solutions. As you grow someone and guide them on how to arrive at solutions that align with your vision, you have someone you can transfer more responsibility to. So investing the time and energy is not a waste.
If you don't have the time, then delegate to someone who has the skills, context and time to help.
Listen and acknowledge! (repeating this point because it is crucial). You are their link to the company, and they don't usually get a lot of time with you. Show you appreciate their time as much as they value yours. If they are telling you something, it is because it weighs heavily on their minds.

As someone being managed, some things to keep in mind:

Your manager is probably busy fighting a hundred fires and is short on time so doing the prep work and getting to the point is a good idea. It not only helps things to run smoothly but demonstrates that you respect their time and are worth investing in.

Be proactive. Before talking to your manager, think through the problem and work through some ideas in your head. You don't have to present the right solution, you just need to show you have put some effort into trying to solve it yourself. In the meeting say things like "I have thought about X and Y, but we can't do that because of Z."
Your manager is not your therapist. Make sure your meetings don't degenerate into a therapy session, stay at the professional, problem-solving level.
Since your manager is short on time, plan your meeting. "What do I want to cover? What order should I present this information? How can I be more succinct?" Role-play the meeting in your head and then reviewing how it went after is helpful. Initially, your rehearsal may not look like the real meeting, but as you get to know your manager, you will hopefully be able to anticipate what they will think/say and then be able to make decisions more confidently on your own.