yes you're right.
Take a look at "basename --help". It looks like it removes any directory name.
I think you should make a list of directories, visit them one after the other and once there process the files inside.
This command should be helpful:
typing just it shows you all the directories inside the PWD and down.
for i in `find -type d`
for j in *.m4a
base=`basename "$j" .m4a`
faad -o - "$i" | lame -h -b 192 - "$base.mp3"