I hear your pain. I too have AA feet (and 5A heels) which manufacturers of fashionable shoes don't want to cater for. I've been told that directly and unambiguously by shoe store personnel.

As far as atheletic shoes; I find that Easy Spirits are my best bet. The come in narrow and since they lace all the way up are pretty flexible as to fit.

MKK