Agile Messenger will work, but it does depend on whether your carrier allows any ports to connect. Seems Vodafone NZ only allows things like http, pop and imap. I can't get an MSN connection over their GPRS network at all.
Ben, does the "G" symbol appear when you try to connect? and have you set up the access point correct?.
When i first used Agile.M it asks how you would like to connect. I used my standard GPRS Internet connection. When you see the G appear with a square around it on the top right of the screen,(with 6600) you know it is connected.