Nokia Internet Tablet N8XX     

Вроде самый очевидный (для гиков) софт для перекодирования это ffmpeg, если нужен гр. интерфейс, то avidemux.
При кодировании (перекодировании) можно выделить следующие шаги:

1. Фильтрация аудио (если исходник нормальный, пропускаем этот шаг).
1a. Устранение шумов.
1b. Восстановление баланса.
1c. Изменение количества каналов.
2. Фильтрация видео.
2a. Устранение шумов.
2b. Восстановление яркости/контрасности и т.п.
2c. Обрезание полей и изменение разрешения под задачу.
3. Сжатие аудио потока (если не фильтровали и все устраивает то пропускаем).
4. Сжатие видео потока.
5. Синхронизация потоков (обычно не требуется).

Если у нас нормальный исходник (dvd, рипы в mpeg4 и т.д.), т.е. устраивает качество видео, звука, а так же размер звуковой дорожки, тогда остается только подогнать этот исходник под формат гаджета. Для этого мы выполняем шаги: 2c, 4 и, возможно, 5. В 2c надо понимать что мы можем обрезать не только черные поля, но и часть полезного изображения, для того что бы уместить ролик во весь экран таблетки, я так делаю и не вижу в этом криминала. Для сжатия вы можете выбрать любой доступный кодек, я использую xvid. Настроект там дохрена, по началу вам придется потратить очень много времени, что разобраться во всех тонкостях. Можете воспользоваться инетом, в качестве помошника по опциям кодека. Для начала используйте настройки по умолчанию и варьируйте только качество сжатия. Используйте двухпроходное кодирование.

p.s. Еще раз напомню, что я, для перекодирования видео, использую avidemux.

..bw

В avidemux: Видео -> фильтры -> субтитры

А я вот это использую:
https://garage.maemo.org/projects/mediaconverter/   
или mencoder.