I tried to breadboard a DC-DC converter and it didn't work either.
I soldered it onto proto-board and it worked fine. They are usually sensitive to the resistance, flakey connections and capacitance in the breadboard.
You shouldn't really attempt to run anything near 5A through a breadboard, 1A is really the limit.
Try implementing the "Typical application" circuit in the datasheet on a bit of proto board and see if it works.