Ok, I managed to find the root cause, and a workaround of sorts.
I took my phone into the Apple store. They hadn't seen the problem before, but they were able to find a few other threads describing the same issue:
https://discussions.apple.com/thread/4404114?start=0&tstart=0
https://discussions.apple.com/thread/4383813?start=0&tstart=0
The one thing all the threads have in common is that the phone receiving the video is older (specifically, a 3GS). The Apple staff said it's probably because the newer iPhones are generating video in a format which the 3GS does not support. This is despite the 3GS being able to play the video within the Messages app, which is a bit odd.
This theory appeared to be confirmed when I inspected the video on my Apple Mac - when I right click and choose "Get Info", the newer videos which have this issue are 540 x 960 and generated in iOS 6.1.3, while the older videos which don't have the issue are 272 x 480 and generated in older versions of iOS. So the picture quality has increased. This is despite the videos being generated by the same physical phone (I'm pretty sure they are anyway).
Based on this hint, I was able to get the videos into my 3GS's Camera Roll by converting the format of the video as follows:
- Copy the video to an Apple Mac (you can do this by connecting the iPhone to the Mac via USB, and then running Image Capture.app on the Mac).
- Open the video in Quicktime.app (in my case, I'm running v10.2)
- Choose File > Export > Format > "iPod touch and iPhone 3GS". This generates a copy of the video in .m4v format (MPEG-4) optimized for iPhone 3GS.
- Copy the new video back to the phone [*]
- Tap the Share button, and voila - Save to Camera Roll option is there and works as expected.
If you don't have an Apple Mac, there may be an equivalent way to convert the video in Windows.
Of course, copying the video on to a computer, converting the video format, and copying it back to the phone might be more trouble than you want to go to just to save it to your Camera Roll!!!
[*] Copying the converted video back to the phone is a bit of a pain. Since I'm using iCloud, I used the Messages app on the Mac to send a message to myself with the video attached [!]. Following this, I could open the video in the Messages app on the phone. An alternative might be to email it to yourself. I also tried copying the video using iTunes, but this was no good: the video ends up in the phone's "Movies" app, which unfortunately plays the video incorrectly in landscape format and appears to have no Share button.
