When I was using Premiere 6 and 7, I noticed the slow mo results were not great. I've since upgraded to v 1.5 and am happy with the results.
For me, the problem was Premiere, because it happened both exporting the project as avi, or frameserving to my mpeg encoder. But the more you slow down the framerate, your video will always suffer slightly.