Christas-
I had a similar problem to what you describe when I received a new 8GB fuze as a gift last Christmas. I had the most recent firmware, used the accepted video format, and used SMC but my videos would freeze after a minute or two of playback. When the included music video also froze, I decided that the issue was beyond fixing through formatting. I made a post similar to yours and did not get a response, so I assumed this was a very isolated problem. After contacting Sandisk customer service and their fixes did not help, I contacted Amazon and they sent me a new one. Using the same videos and SMC, the videos now work flawlessly.
Good luck.
MRR