Possibly a proxy between your server and AOLs users is doing something wrong.
A traceroute from an affected user to your server should indicate where the connection is failing, so this is probably the next best step.
If the traceroute fails:
a) within an AOL controlled network
- get the user to contact AOL, preferably with a message written by someone who understands the nature of the problem (i.e. you write on behalf of the user)
b) within a network which you either control or have some say in (for example, your data centre's network)
- take whatever action seems necessary (i.e. try and get it fixed yourself or inform the data centre's techs)
c) anywhere else
- just sit back and wait as you'll most likely be able to do nothing and the problem should get resolved some time
Either way, if it's down to a) or c), you can reassure the users that it's not a problem with your kit.