Потоковое в Android это боль в заднице.Наилучшим вариантом является потоковое видео по протоколу RTSP.
Если ваш Droid обновлен до версии 2.2, вы также можете настроить простую веб-страницу со встроенным Flash-плеером, например, jwplayer (не забудьте настроить альтернативный контент).если на устройстве не установлен Flash Player, чтобы пользователь мог загрузить его с Adobe).
Я успешно развернул оба решения.RTSP для <2.1 и встроенный проигрыватель Flash, воспроизводящий видео из потока RTMP (вы также можете воспроизводить локальный файл с сервера) </p>
Обратите внимание, что на некоторых устройствах (Hero) вы не можете встроить WebView с помощью проигрывателя Flash внутриваше приложение.
Если вы ищете быстрое решение, я бы попробовал 3gp.
Кроме того, если подключение недостаточно быстрое для воспроизведения видео, вы получите ту же ошибку, которую вы опубликовали.(даже с правильно закодированными видео).
РЕДАКТИРОВАТЬ: я использовал H.264 на потоках RTSP и VP6 на RTMP.VP8 поддерживается только новыми устройствами.