matchkamph, I use VirtualDub to pre-process video prior to amv conversion there is a guide to using it
HERE
You can crop, resize and adjust framerate etc.
You can download it
HERE
Obviously for full screen 128x128 you need to crop a fair amount of the sides because you are going from a 4x3 ratio to a 4x4 otherwise the image will be compressed and everthing will appear tall and thin.
You can edit the images in your firmware yourself and create a new background and icons but it will still be the same layout.
You need to first extract your firmware from your player using s1fwx.
Download
HERE
Guide
HERE
Then you can change the images using s1res
Download
HERE
Guide
HERE
Then reload your firmware to your player using MP3 Player Utilities Update Tool
Download
HERE
Guide
HERE