I am not sure if this will solve your problem, but I hope it gives you a metodology to solve it.
1) You need to define what "looks really bad" means.
Contrast. Too much contrast? Too low?
Color. Has the color shifted?
Problems with saturation? Do they look pale? Or oversaturated?
Does the problem occur with all colors? Or just with some vibrating colors like neon green, or red?
Sometime ago you needed to adjust the gamma to some video files. Does the images look specially bright? Or specially dark? (Correct the gamma)
2) Find out if the video is actually using NTSC. Probably is digital. If it is digital there is no need to look for a NTSC profile.
3) Review your color calibration settings. Use a Web/Internet settings, not a press settings.
4) Be sure you are not using a cmyk export on the jpg files.
5) Try to send a color chart or color bars and see how it is displayed.
http://en.wikipedia.org/wiki/File:SMPTE_Color_Bars_16x9.svg
6) Turn off the Include ICC profile. And see the results.
Some problems can be just that your monitor has better quaility than the tv they are using, some could be their system is not recognizing the colour profile, or just droping any.