I find that when I had to deal with some of my old isp's, that when speaking to them about speed upgrades every department that I contacted basically refused my requests until I contacted the billing department, I dont know what the billing departments has to do with speed upgrades, but with Freeserve and wanadoo and orange although they are basically the same isp, I only ever got upgraded in speed when I talked to the billing department and they would put through the speed upgrade request, sometimes I waited 10 days for the speed to go up, and on one occassion 10 minutes after I called them i went up from 1mb to 2mb.
My advice, get onto AOL billing department, if they give you hassle, threaten to cancel your contract and see how far they go to keep you as a customer.
I dont know how good Gay O L will be for Customer Service now that the uber shite carphone warehouse has bought them out, but I would still give them a call, but if I was you, i wouldnt be calling them to get a speed upgrade, I would be calling them for a MAC code.