Ok, I figured out the trick with USB sticks, you cannot format the whole device with a filesystem, you have to use partitions. You can make the whole device a single partition and put the filesystem on it and the works, that's what I did on the 2GB stick and it worked, but you can't put a filesystem on the whole device with no partitions, that won't work.
I confirmed this by taking a 16GB stick and making four 4GB partitions and put some mp4's on each partition and they all played fine.
Sure would be nice if this was documented someplace...