SpaceX is not competing with NASA, because NASA doesn't make rockets. NASA has input on the design requirements, but all the real work is done by private contractors, like Lockheed and Boeing. SpaceX is just a new contractor and they operate just like the others. They have some interesting new engineering approaches that may reduce costs, but it's not any fundamentally new business model.
Actually, it is a fundamentally different business model. You are correct that it was always private companies that did the final design and construction of the rockets, but historically Congress forced many decisions on NASA based largely on spreading the money around. For instance, NASA wanted the Space Shuttle to use liquid fueled boosters, but Congress insisted on the SRBs specifically so Thiokol Corporation of Utah would get the business. The same thing is happening with the STS under development now. Congress is forcing NASA to use Shuttle components in the first generation STS specifically to funnel money into certain congressional districts. Under the non-commercial contracts, Congress and NASA actually make design decisions that may not be optimum from an engineering perspective.
The rules under which SpaceX performs NASA missions, are much different. NASA does not get involved in the design of the rocket/spacecraft beyond listing requirements that must be met. Some seed money is provided, for companies that win bids to compete. But ultimately the winners are paid a fixed price - which is also a big difference. Historically, these contracts were cost plus. This new approach does appear to be saving money and it is also leading to competing designs which is interesting as well. For instance with commercial crew, Boeing is building a fairly conventual capsule that lands under parachute, Sierra Nevada is building a lifting body that will reenter and glide like the shuttle, and SpaceX is building a capsule that will land propulsively (parahutes will only be deployed if there is a malfunction in the engines.)