Of course, the best solution to this problem is not to have it in the first place. Being proactive and thinking about the future is sometimes a rare talent, especially in 18 year olds fresh out of high school, but then again grad school is supposed to select the exceptional individuals.
There is a world of difference between a recommendation from someone you worked with, and from a mere acquaintance. The latter kind rarely benefits your application in a meaningful way, and can sometimes even hurt it. No matter how enthusiastic your instructor is, unless the course is at least a project-centric course (eg. grade is based entirely on your individual term project), they will not be able to make a good, in depth argument for your abilities, and the recommendation will therefore be weak.
The point of the recommendation is that the admissions committee will read it, and decide whether you have potential to be a good researcher. How can they, if the recommendation does not talk about your research at all? And how much better if instead of hinting at your potential indirectly by citing course performance, the recommender can just say "this person has potential to be a great researcher because I have personally seen that they are good at research"?
This is why there is a qualitative difference. This can be a big problem when applying to a very selective program. What if you apply to a program where the committee has a philosophy that "an application is only as strong as its weakest link"? Even if you are quite exceptional otherwise, you can get eliminated early on because there are many other applicants who are also exceptional, but don't have a recommendation problem.
Also, similar to how a lukewarm recommendation can mean "I think this person is a bad candidate, but I am not being negative out of politeness", a recommendation from someone who only taught a course can mean "this person is a slacker who never bothered to do real work, so they can't find any supervisors to recommend them".
The best way to remedy is really to obtain more "good" recommenders. Because you want people who supervised you, the solution is obvious: You haven't been supervised by enough people who will vouch for you; you must undertake more projects and be supervised by other people whose recommendation will carry weight.
If still in school, look for faculty whose lab you can work in. If that is difficult, try approaching a former (or current) instructor with an idea for a theoretical or computational project (this requires less commitment from them, so they may be easier to convince). It doesn't necessarily have to be original research, so long as you can come up with a relatively long term (at least half a year) project where you are the primary contributor. It could also be (more) valuable to spend a summer working in a lab at a different university.
If out of school, delay your application by 1-3 years, and look for work as a lab tech at a university, institute or private company. Make sure not to displease your boss.
A related problem is working for a long time with the same person, for instance an undergrad who spends 3 years in the same lab. This is actually better, because you can accomplish much more in 3 years, and you can have a very impressive project to sell yourself with. The issue is that you will have only one supervisor - but hopefully after 3 years, you will have networked with collaborators and other scientists and will not have a problem there.
