I look at some of the largest start-ups or even companies, and they aren't solving problems so much as creating opportunities.
AirBnB didn't really solve a problem, they created an opportunity for you to rent your extra space, or find a place other than a hotel to stay.
This also applies to larger companies. Coca-cola didn't solve a problem, they just made something people really liked.
Apple and Microsoft didn't solve a problem people had. They didn't have computers, so what what problem could you have been solving by giving people an operating system. At the time, people didn't know what they would use a computer for, so what problem was being solved.