Personally i use tweetdeck on both my iPhone and Mac.

iTwitter push notification only works when receiving DM and mention. But there is a catch, push notification only works when receiving DM and mentions from another iTwitter user.

Other Twitter related push notification apps are:
1. IM+ ($4.99) is a instant messaging apps that are the first apps that provide twitter push notification.
2. Tweet Push ($0.99 + $0.99/months/account) - that pushes your tweets but is not a full-fledged Twitter client. Instead, it uses your preferred Twitter client (Twittelator, Tweetie, Twitterfon or Twitterrific).  this is subscription based, It'll cost 99 cents every month for each Twitter account you want to use it on - Not recommended
3. Boxcar ($2.99) checks your Twitter account every 2 minutes for mentions and DM and Push you the message AND let you see it in your preferred Twitter client like Tweet Push
4. Twitbit ($4.99) is a full fledge twitter client that allows you to receive push notifications for mentions and DM
5. iTweetreply ($1.99) similar to boxcar, it allows u to link it to your other primary twitter applications. The application itself is a simple sms like twitter applications

There are some other push notification application that should work with twitter too, e.g. Fring (Free) - not too sure on how long it will stay connected and whether it will push twitter messages to you.