Reader Mike Dred posted a link to an article he wrote about why your iPod video cable might not work. iPod skins topped his list, preventing cables from seating properly in their jacks:
By removing the iSkin from the proximity of the iPod Headphone jack the demons were gone and I was watching great quality podcasts and movies on a giant screen from my iPod with good audio.
Other problems include using defective cables, forgetting to set TV Out to On, using the wrong system for your TV (NTSC for North America, PAL for Europe and Australia), and mis-setting the Widescreen option. Follow the link and read it all.