Another vote for Palingo. I like how it syncs with Facebook and my address book. Its IM interface is pretty good, and I like how it tells you when the other person is typing. The only thing is i wish it was easier to switch between chats, if you have more than one open. It also keeps you logged in while its not open, which is nice, and it alerts you via text message if you get an IM.
Apparently Beejive IM uses Push to send you an email telling you you have an IM, which im not too fond of. I'd rather clutter up my SMS inbox than my email inbox.