I'm experiencing a similar problem. We've produced an app that plays videos on some Samsung S phones but not others. Any help or direction you might give would be greatly appreciated. Here's the MediaInfo dump:
-----------------------------
General
Complete name basic.mp4
Format : MPEG-4
Format profile : Base Media / Version 2
Codec ID : mp42
File size : 22.6 MiB
Duration : 2mn 23s
Overall bit rate : 1 318 Kbps
Encoded date : UTC 2010-07-16 16:39:50
Tagged date : UTC 2010-07-16 16:39:53
Video
ID : 1
Format : AVC
Format/Info : Advanced Video Codec
Format profile :
Main@L3.1
Format settings, CABAC : No
Format settings, ReFrames : 2 frames
Codec ID : avc1
Codec ID/Info : Advanced Video Coding
Duration : 2mn 23s
Bit rate mode : Variable
Bit rate : 1 153 Kbps
Width : 960 pixels
Height : 540 pixels
Display aspect ratio : 16:9
Frame rate mode : Constant
Frame rate : 23.976 fps
Color space : YUV
Chroma subsampling : 4:2:0
Bit depth : 8 bits
Scan type : Progressive
Bits/(Pixel*Frame) : 0.093
Stream size : 19.8 MiB (87%)
Language : English
Encoded date : UTC 2010-07-16 16:39:50
Tagged date : UTC 2010-07-16 16:39:53
Color primaries : BT.709-5, BT.1361, IEC 61966-2-4, SMPTE RP177
Transfer characteristics : BT.709-5, BT.1361
Matrix coefficients : BT.709-5, BT.1361, IEC 61966-2-4 709, SMPTE RP177
Audio
ID : 2
Format : AAC
Format/Info : Advanced Audio Codec
Format profile : LC
Codec ID : 40
Duration : 2mn 23s
Bit rate mode : Constant
Bit rate : 160 Kbps
Channel(s) : 2 channels
Channel positions : Front: L R
Sampling rate : 48.0 KHz
Compression mode : Lossy
Stream size : 2.74 MiB (12%)
Language : English
Encoded date : UTC 2010-07-16 16:39:50
Tagged date : UTC 2010-07-16 16:39:53
---------------------------------------------