Make sure to install both mplayer and lame. To do this open a terminal (Ctrl+Alt+T or Super+T) and paste (Ctrl+Shift+V) the following line and hit Enter to run:
sudo apt-get install mplayer lame
Enter your password when prompted, then navigate to the folder containing your WMAs and run the following command in the same terminal:
for i in *.wma ; do mplayer -vo null -vc dummy -af resample=44100 -ao pcm:waveheader "$i" && lame -m j -h --vbr-new -b 320 audiodump.wav -o "`basename "$i" .wma`.mp3"; done; rm -f audiodump.wav
This will create 320 kbps MP3s in the same directory, keeping the original files.
These MP3s will not contain ID3 data (title, artist, album, etc). GMusicBrowser is excellent for modifying this information.
Thanks to Rory Alsop for the one-line script, which needed a slight update. Here he also shows a way to make a single command run the script.