UPDATED:
I went the 3gp route and changed the audio settings. I got it to play back smoothly.
Format: 3PG
Codec: Apple MPEG4 Decompressor
Res: 800x450
Audio: AAC, Mono, 16.0000kHz
Size: 127 MB
DataRate: 4000kbps (4Mbps)
Click here to download video
Here is MP4 format that I got to work finally. Awesome video quality. Audio overall on this device blows.
Format: MP4
Codec: MPEG4
Res: 800x450
Audio: AAC, Mono, 16.0000kHz
Size: 164 MB
DataRate: High Variable Rate
I hope this helps people. I'm determined to encode video in h.264 and have smooth playback, but I'm not sure what I'm doing wrong.