I just tried that AOL mobile. The AOL version does work and has many other integrated features relevant to having an AOL account, but it is slow and hogs a lot of memory and cpu power.
Per the first poster's mention I tried Slick. Boy, that is slick! Handles all the main IM's out there and seems to do an ok job.
Get Slick Here
I also Googled "mobile IM" programs and found these free Im's. I've not tried them, but thought I'd post 'em since he asked for suggestions....
Fring Sort of interesting. Mogul is compatible.
Agile Mogul approved