Yeah I would think its the class of the card. Try class 4 or 6. I think they work the best.
I stopped using sandisk when my sandisk titanium stopped working all of a sudden :P
I don't think formatting it would make any difference but yeah Its worth a try.
I would say get a higher class of the sdhc.
I myself use lexar and it is working alright so far, no music stuttering or anything.. so far..