Re-visiting after a while I feel another answer is justified.
You are actually asking several distinct questions:
- How did George W. Bush make torture legal?
- What did Obama undo?
- How did government organizations get away with using torture?
I'll answer the first and the third one.
In your post you make a statement which already contradicts the premise of the first question:
"Obviously it was illegal."
I fully agree with your own statement: The government (Bush, congress) didn't make torture legal, because they couldn't. Nobody can. Torture is illegal and stays illegal. This is even though there were written laws and interpretations allowing torture, or denying that e.g. waterboarding is torture.
It is unusual to claim that a body of law and law interpretation which has been produced in a process conformant with the constitutional rules — the positive law — does not constitute applicable law. Such claims are only made when the results of the legal process deviate far from commonly accepted "self-evident" principles — usually human rights —, even though their conception was formally compliant and the resulting law forms a formally consistent body. The key is "self-evident". A sensible individual could simply tell that the written law was not abiding by commonly required standards.
The GDR soldiers killing fugitives climbing the Berlin wall were sentenced with such an argument because they did nothing forbidden according to GDR law. In its decision, the highest German court applied formerly established principles:
"Der Widerspruch des positiven Gesetzes zur Gerechtigkeit muß so unerträglich sein, daß das Gesetz als unrichtiges Recht der Gerechtigkeit zu weichen hat" ("the discrepance between the positive law and actual justice must be so unbearable that the statute as incorrect law has to yield to justice").
Another famous example is the prosecution of crimes committed by the National Socialist government.
Of course "actual justice" is in the eye of the beholder: It is no coincidence that both trials happened after a nation and its legal system ceased to exist. Positive law, even one as rotten as the Nazis's, is usually a formalization of the perceived "actual justice" of a government and its people; its actual injustice is a difference to a different frame of reference. One needs to assume an outside view to perceive that injustice.
This realization is the key to answer your question how the government got away with torture: The U.S. still exists. The uninterrupted line of succession from the government that declared torture legal makes it unlikely that "the positive law yield to justice". No American government will conduct the equivalent of the Nuremberg trials or even the "Berlin Wall guards" trials against former presidents or John Yoo, at least not before the revolution.