The kicker is environmental change.
http://en.wikipedia.org/wiki/File:Last_glacial_vegetation_map.png
Hunting by humans certainly didn't help any. But with the retreat of the glaciers, cold-adapted megafauna lost their habitat, and megafauna-eating predators lost their food supply, and extinction and so on.
What's needed is some way to 'settle' the megafauna someplace more hospitable- northern Canada, maybe? But it's covered with glaciers when it's cold, and when it's not, it's barren at least for a while, and temperatures inhospitably warm where these critters live. Basically, the most 'robust' way to save the Pleistocene megafauna would require, at least, pretty hefty aberrant behavior of Earth processes.
If you still want to write the TL (and you so totally should,) you could just hop over the nitty-gritty of the extinction and get to the meat of things (no pun intended.) You could say that there was a minor (as in, smaller than OTL,) extinction, and have the critters running around be descendants of the Pleistocene megafauna. Pretty much all the interesting groups had representatives that lived in (relatively) temperate climates. As people have pointed out, many megafauna have 'human-useful' analogues/relatives, so at the very least some (horses, camels) might be domesticated/made useful to humans.
Go for it! The idea's too good to get held up before leaving the house.