Pretty cool that it works in Wine! It's always good to hear that useful software is functional in Wine; the more of that we have, the easier it'll be for some of us to stop using Windows...
MP3 can actually have fairly high quality, as long as a good encoder (like Lame), and VBR with a high maximum bitrate are used. It's hard for me to distinguish high-bitrate VBR from the original recording. 128kbps mp3s very often sound like crap to me, though. Can Atrac3plus do VBR?
Too bad it doesn't support Ogg
Hard to find inexpensive portables that do.