I had been using the 8GB Class 2 card that came with the Desire, and videos would play fine from it.
I recently switched to a Class 4 8GB card I had purchased for my last phone and now videos stutter during playback.
All I did was copy the files from my original card to my desktop, reformatted the Class 4 card and then copied those files to that card.
I have tried viewing them in both Rockplayer and Vplayer, and the videos are usually in either an .avi, .mp4 or .wmv format. They are hit or miss among the different formats as to what will stutter or not stutter.
edit - I just found a good video converter and it seems to have taken care of it