One of the things that bugged me about the movie was the idea that falling into a black hole could send you back in time. Well, that bugged me after I got over the fact that a black hole with at little initial mass as those shouldn't be sucking in anything not directly in its own trajectory. But I got to thinking: If a ship fell past the event horizon while attempting to escape at high warp, then the slingshot effect might begin to take hold---the ship would begin moving back in time, just like it was going around a sun. Except.....this is a very new black hole. So as soon as the time reversal begins, suddenly the black hole isn't there anymore. This would represent an enormous warp breakaway and might just be enough to fling a ship through space as well as time to the distant locations Spock and Nero ended up.
Sometimes a black hole is just a black hole, but sometime may allow travel... http://www.wired.com/science/discoveries/news/2003/04/58359
I think it may be fair to say that black holes rarely exist in their pure destroy-everything-nothing-escapes state in the Star Trek universe(s). They quite often act as worm holes that join distant places and may also traverse time, forward or back. If there's a way to use a black hole - even a new one - to effect time travel, I'm sure Spock could figure out the math.
Well, since current science has no means of verifying what happens when you do pass an event horizon of a Black Hole, it could take you back in time. Or it could take you forward in time. Or it could convert you into cheeze. We just dont know, and unless someone built an FTL ship in their garage, we wont know for a looonnnnnng time.
Current science actually does have some fairly reasonable models of what a fall into a black hole would look like: http://casa.colorado.edu/~ajsh/schw.shtml But the mystery is what happens at the singularity itself. That's the part we don't have a clue about.
There are multiple ways it could have gone down. As SonicRanger pointed out, there are types of singularities that can spawn wormholes, and wormholes can readily become time machines if the two ends are in different reference frames. If we don't want to go the wormhole route, we could also say that warp fields, being themselves a distortion of spacetime, act as a sort of multiplier to the gravitational curvature of a black hole (or the sun, if you want to bring ST IV into it.) So you can treat the singularity as if it was a Tipler cylinder or some other utterly massive object, which is typically what physicists use for timelike curve, slingshot-style time travel.