I've never tried the "Include Videos" option, but if it's not working, try drag-n-dropping the videos into your iTunes movies folder.
Try syncing your iPod again, making sure that you've got the videos checked in the Movies tab on your iPod's page in iTunes.