OK, I installed the Aeolus style on my board. It worked as expected and the upload avatars field showed up. So you might check to see if your db is reflecting the correct setting. Go to phpbb_config and find the field "allow_avatar_upload" and make sure the value is set to "1".
If that is the case then I would suggest reuploaded the profile.php from the orignal download of the board. See if that fixes the problem.
The only real thing that is different about your setup from mine, that I can tell, is how you handle uploads. You said
Avatar Storage Path :
Avatar Gallery Path
I have my uploadable avatar path as images/avatars and my gallery path as images/avatars/gallery and then have category folders directly below that. I wonder if having your upload directory within your "gallery" area is affecting the uploads. I wouldn't think it would but who knows.