I just changed mine 3 seconds ago. I've been having the same problem, but found the solution.
1. Get Paint.net (this is important later)
2. Open up the image you want as your avatar
3. Select it and copy it.
4. Make a New image, make it's resolutions 74x74 (75 wasn't working for me)
5. Paste the image, and resize it to fit.
6. This is why paint.net is important: go to Save As and save it as a .png file. Then it will bring up a rendering menu with 4 options: Auto-Detect, 32 bit, 24 bit and 8 bit. There's also a few options below it. Modify these until the file size is less than 5 KB.
Then the avatar should work.
EDIT: If you're on Google Chrome, you should see a black bar in the corner that says Uploading: x%.