eBuddy [iTunes link] could be the answer I'm looking for. It supports AIM, MSN, Yahoo, Google Talk, Facebook Chat and ICQ. If you're familiar with the free version of AIM, it's very similar in form and function. It has the bare essentials along with some custom emoticons. It does not feature picture messaging or voice messaging like Palringo.
The one thing I liked about the AIM app is that your push notification includes part of the IM that it's pushing and the screen name of your buddy. eBuddy has a more generic notification saying that you have received an instant message. However, the eBuddy app actually opens faster than AIM when you want to view your IM in full.
Like Palringo, you have to register with eBuddy with a screen name and password before you can use the app. It's FREE so try it out!
UPDATE: The eBuddy experiment has failed. After exiting the app, eBuddy will only let you stay logged in for up to 30 minutes. If you're not logged in, you can't get push notifications. AIM allows you stay logged on for up to 24 hours. All you have to do is log in once a day to be perpetually online on AIM.