Following some further investigation, I've found the following information that can hopefully help other people get HLS streaming on Android working.
Encoding - The video encoding, and the segmentation setup can have a large impact on the Android versions that the video supports. I ended up creating a video using HandBrake, with the following settings:
MP4 File
H.264; Baseline Profile; Level 3
AAC Audio; 44.1k; 128bit (Note: I found that JellyBean was a lot more picky about the audio than ICS/Honeycomb. Some audio bitrates would create videos that Jellybean would not play at all. In general Mono and low bitrate audio seemed to work better on Jellybean).
Segmentation - Using the Apple MediaFileSegmenter, I found adding the "-no-floating-point-duration" and "-z none" flags allowed me to create a video that worked across Android 3.0->4.2
Gingerbread - I was unable to get Android 2.3 to work with HLS out of the box, but I did find that using the Vitamio library worked pretty well (see this question for further info)