blubergeist,
If the original video is widescreen letterbox style with black areas at the top and bottom then you need to crop the video with a program like VirtualDub before you convert it.
You also need to crop the sides for 128x128 so that you get this,
instead of this
There is a guide to using VirtualDub
HERE
and you can download it
HERE