How to build relationships with professors in such a way that results in good letters of recommendation?
Strong recommendation letters come from professional relationships, rather than personal relationships.  Of course, the two are often related, but if a professor hasn't seen much more than getting an A in a class from a professional perspective, then they can't say that they have.  A wise and helpful faculty member will warn you of this fact in advance, but faculty are human and many may not be wise enough or  helpful enough to give an appropriate warning.

The canonical answer, of course, for getting a good recommendation to grad school is to work with a professor on an actual research project.  What you actually need, however, is for a professor to be able to speak to your potential to become a good researcher.  Even working on a research project will not necessarily demonstrate that, if your role is as a cog in somebody's machine (a friend once worked on a research project as an undergraduate where her job was literally to grind rocks into powder with a mortar and pestle: the project was awesome, the job they wanted done was not).

What does research potential really consist of?  In my experience, research potential means:


Creativity in approaching difficult or ill-defined problems
Initiative enough to accomplish hard work work independently
Skill enough to solve complex problems effectively
Intelligence and background enough to acquire new skills when needed
Social skills enough to do all of these things as part of a team (semi-optional)


There is another excellent way besides actual research projects to demonstrate all of these as an undergraduate: project-centric classes.  Many graduate or upper-level undergraduate classes have an large optional or required capstone project.  When you take on such a project, it gives you a chance to do something really cool, above and beyond the base minimum.  With a good project, you can demonstrate all of these qualities to your professor and provide both the evidence and the motivation to write a really good letter.