Development on pine is dead, long live alpine! Alpine is a fork of the pine code under the Apache license. It has much better UTF-8 support. Give it a try and let me know how you love/hate it.
Update: I have upgraded Alpine to the new 1.0 release. I have also changed the global pine/alpine configuration to use IMAP access to prevent multi-access problems with webmail and pine. It will now prompt you for your NERP login and password when you first startup the program.