This is most likely due to pine's lack of UTF-8 character encoding. Setting your terminal to use "Central European" for it's character encoding should fix this. This is different depending on the terminal you're using, however if you're using our default GNOME setup with gnome-terminal you can do this as follows:
- From gnome-terminal's menu, select select Terminal->Set Character Encoding->Add or Remove.
- Select Western (ISO-8858-1)from the left menu and click Add.
- Click Close.
- From gnome-terminal's menu, select Terminal->Set Character Encoding->Western (ISO-8858-1).
- If your mail client is open, you will have to close it and reopen it.