After mucking around abit, found a neat solution.
First up install soundconverter which gives you a nice GUI to play with.
sudo apt-get install soundconverter
Then install gstreamer plugins with the appropriate codecs & encoders
# This package contains the aac encoder
sudo apt-get install gstreamer0.10-plugins-bad-multiverse
# This package contains the mp3 encoder
sudo apt-get install gstreamer0.10-plugins-ugly-multiverse
Go ahead and enjoy your conversions!