Possibly you are burning m3u files which will not work as they are only playlist files and not mp3s which you should be burning. This thread describes what you should do for audio files. [EDIT It's just been updated and looks like an EXCELLENT job]
http://www.gnutellaforums.com/showth...threadid=25972
Videos get a bit more complicated as the type and make of Disc you use can be important. Ask if you need more help but try burning audio first.
I hope this helps