Ah. Yeah. Might be a format problem. Just after that post, I found one of my videos wouldn't show a thumbnail and just had the loading animation, though it works fine on my desktop.
And changing it to MP4 is unlikely to work - most likely already *IS* MP4. It's other aspects of the codec that's the problem. For example, the video that failed to load for me is showing as "MPEG-4 Video (DX50)", while the other movie on my Arc is working fine, but is an "MPEG-4 Video (XVID)".
Possible solution: Grab "VLC for Android Beta" by "VideoLabs - VideoLAN" off the Play Store. Just tried it and it played the video that the Gallery couldn't.