Its true that the iTunes videos cannot be played on the Storm, and I havent figured out how to convert them.
I use DVD fab5 and Handbrake to rip/convert videos from my DVD collection, it works well. There are other ways to do it, search the forums.
I dont know if there is a web site to go to to download videos that are playable by the Storm media player. If anyone know of a place to download videos, please let us know.