(Video gurus: feel free to correct me here.

)
Think about what's happening in this example. You have a one second clip where all that happens is that a circle moves from the left side of the screen to the right side. You've got 24 frames with a circle on each one in a slightly different position.
Now slow the clip down so the circle moves from left to right in 5 seconds instead of one. You will need 24 * 5 = 120 frames...but you only have 24. Where do the other 96 come from?
Premiere and most other NLEs (the exception is maybe Vegas) take the easy way out: they just duplicate each frame until the time span is filled. In this example, the first frame will be copied four times (total of five copies), same for the second frame and so on. Each of the original frames will show for 0.20 (5/24) second instead of 0.04 (1/24) second. Which is why the slowdown looks jumpy.
(If you're using 30 fps interlaced material, then you have another problem: the frame copying screws up the 3:2 sequencing.)
A solution is to somehow create those inbetween frames accurately instead of just copying the ones you have. That's not too difficult if all you have is a circle moving across the screen. Anything more complex is virtually impossible (think of completely re-animating the clip).
Video Vegas claims to create these inbetween frames by extrapolation, but I'm skeptical of the results. I tried it with a complex clip that had several moving elements. Some of the elements were smoothed, but most were not. It may work with a very simple scene, however.