Just abxed 'Crystal Method - Born too slow' in ogg vorbis and aac, and got these results:
11/12 0.3% Chance of Guess
Its only one song, but the aac sounded MUCH worse, with pre-echos. Just thought you'd like to know...
Can you upload a sample?
HE-AAC has a very poor temporal resolution. Pre-echo and smearing is really terrible in my opinion. Your results are therefore not surprising.