I've been having the same problem with my 1G nano. Usually happens for a few seconds every 5-10 minutes. Switching headphones doesn't fix the problem (I thought it might be a problem with my lanyard phones, but it wasn't). I'm glad at least one other person has this problem. But a solution would be nice!
I have the same problem, limited to podcasts. When I rewind to before the stuttering happens the stutter isn't replicated. They play fine in iTunes and the stuttering problem only seems to occur on the initial playing of the podcast.
Haven't had the problem since I updated to software version 1.3, they must have fixed it.
Chundles, you seem to be correct. I upgraded to version 1.3 and have not had the problem since. Thanks for the suggestion. (And yes, mad_jew, I only ever encountered the stuttering problem on podcasts.)