Okay, this is a hack, but I got it working (for Dapper Update 1 - Edgy couldn't be to dissimilar)
VLC on ubuntu repositories (0.8.4, or the dapper nightlies 0.8.5) appears to be not compiled with AAC encoder support. I didn't have too much luck trying to compile it myself (kept breaking some library or the other). I looked around and came across the vlc version for slackware - all ready and good to go
So I looked for info on installing .tgz packages in ubuntu and came across "alien" and got it to install the package. The slackware version gets installed in /opt/vlc directory. vlc then needs a few library linking to get it working.
Here are the detailed steps that to get you going with transcoding to H264/MP4A and MP4V/MP4A - please, first understand what is going on, and improvise as necessary. DO IT AT YOUR OWN RISK.
download vlc-0.8.5-i686-3.tgz to your home directory.
sudo apt-get install alien
sudo alien -i vlc-0.8.5-i686-3.tgz
examine /opt/vlc directory to understand what has been installed.
add the line "/opt/vlc/lib" (without quotes) to /etc/ld.so.conf
sudo ldconfig
sudo apt-get install libsdl-image1.2 libid3tag0 libslang1 libmad0
sudo ln -s /usr/lib/libpng12.so.0 /usr/lib/libpng.so.3
sudo ln -s /usr/lib/libFLAC.so.7 /usr/lib/libFLAC.so.4
sudo ln -s /usr/lib/libtiff.so.4 /usr/lib/libtiff.so.3
sudo ln -s /opt/vlc/bin/vlc /usr/bin/vlcslack
Use the following command to identify any broken or missing libraries.
vlcslack -v --reset-config --reset-plugins-cache -l
Hope this helps. Leave a note if it did. Good luck.