Original Question

Is there some cli tool to convert aac files from the iTunes Store (no DRM) to mp3?

Update 1

I installed libavcodec-unstripped-52 and get a little further.

When I try to encode MP3 files with it: It says [mp3 @ 0x997cde0]Header missing.

lame also had problems since the tags are ID3v2, is it possible that the libmp3lame does not support that either?

Should I convert the tags or what can I do to get this working?

This went through, but there are no headers in the resulting MP3 file. How can I get the headers in there?

The most appropriate command line tool is the ffmpeg utility available to be installed via the software center/synaptic manager.

A command line example would be something like this for Constant Bitrate Mode (CBR):

ffmpeg -i inputfile.m4a -c:a libmp3lame -ac 2 -b:a 190k outputfile.mp3

Or even better for Variable Bitrate Mode (VBR):

ffmpeg -i inputfile.m4a -c:a libmp3lame -ac 2 -q:a 2 outputfile.mp3

More information on mp3 encoding with FFmpeg can be seen here:

If your Linux complain that he doesn't have an mp3 codec, try this:

ffmpeg -i inputfile.m4a -acodec libmp3lame -ac 2 -ab 160k outputfile.mp3

Note that the -ab parameters takes in bits per second, not kilobits per second.