You have tried converting them on a PC? And that did not work? That's weird. That Note should play a lot of formats. My Galaxy Tab plays MKV, AVI, MPEG, MP4...Its something about those files.
Have you tried using Kies to transfer? That should automatically convert it to a format the Note would read.