I've figured out how to transcode videos for the Samsung Instinct using ffmpeg. The initial problem I had is the standard Ubuntu version of ffmpeg does not include aac support. Fortunately Medibuntu has an ffmpeg package with everything enabled. You'll need to add the medibuntu repositories to your system first. ffmpeg didn't want to upgrade, so I used apt-get to remove it and install it. Be sure you have libfaac installed too.
To verify that you've got the right ffmpeg, run 'ffmpeg -version' and look for --enable-libfaac. If you don't see it in the listed configuration then the following won't work.
Once you have the right ffmpeg you can transcode a video with something like this:
ffmpeg -i BeerBot.avi -acodec aac -ab 128k -vcodec mpeg4 -b 1200k -qscale 4 -async 100 -s 320x240 BeerBot.mp4
Throw BeerBot.mp4 into the MEDIA directory on the SD card, and it will appear in TV/Video, My Videos, Sideloaded. You may need to change the scale (-s flag) if your video has a different aspect ratio. You can go up to 432x240 for wide screen videos.
If you are curious which video I was converting, you can see a version of it here: http://www.youtube.com/watch?v=rDN-OSffLAE