One of the problems with audio codecs is that they may require a rather large amount of floating point math calculation. Ogg Vorbis, an entirely free audio codec that has much clearer sound than WMA or MP3, has the limitation that the basic codec for it requires a lot of floating point math, and thus couldn't be run on devices like StrongARM CPU's that have poor (or no) floating point math capability in hardware.
Recently, a version of Vorbis that does allow use on those processors has come around, but with AAC the challenge might be much more difficult and complex. I wouldn't be surprised if older iPods wound up unable to use a newer format.