I had a similar issue... only it was with Yahoo IM, not AOL or any other. The root cause of my problem was that my office network uses a proxy server. Perhaps your issue is similar. To find if you have a proxy server, go to your internet options and look under the connections tab. Click on "Lan Settings" and you might find something like
http://autoproxy.(your company here).com

port number)
To put this in Trillian:
Trillian Preferences -> Advanced Preferences -> Proxy Server
From there you need to select the right format (e.g. HTTP) and then input the information. The Username and password fields will exist whether you need them or not.
As for Yahoo specifically you may need to change the port on that specific IM engine to port 80 (from 5050). I found this solution in some other posts and it worked for me.
Good Luck