Given my inability to use Amarok 1.4 and my lack of desire to use Amarok 2.0, I tried loads of music players and for now I've landed on aTunes.

It's not perfect. It's far from perfect. But it's the best of the bunch. These are the features I MUST HAVE for a media player and which aTunes possesses.

1. Last.fm integration. aTunes has probably the best integration I've seen in a player, without going over-the-top and stuffing a whole web browser into the app.
2. System tray icon, right-clickable with song controls in the menu.
3. Commandline interface.
4. Able to display CJK fonts. In Arch (or in Gentoo using the icedtea6-bin VM) CJK fonts are displayed as empty boxes, but in Gentoo using Sun JVM, it works fine.
5. Tag editing. aTunes has a pretty nice tag editor for single songs or multiple at once.
6. Amarok-like tree of albums/artists/genres/whatever I want. I want a single expandable and collapsable tree-list, not 3 panes I have to click between.
7. Equalizer.
8. Skins are nice; aTunes has these.
9. "Collection" support and folder-watching/auto-updating when I dump music into ~/music. aTunes does this very well. Scanned a few thousand files fairly quickly, and does updates very fast.
10. Amarok-1.4-like spreadsheetish playlist layout.
11. Lightweight build process. No gstreamer. aTunes provides Mplayer and Xine backends and has few to no other dependencies (besides Java). The Mplayer backend didn't work out very well for me, but Xine works beautifully.

It also has some other nice bonuses, like the elegant way it uses the Album Artist tag for albums with multiple artists, the interesting statistics and bar graphs it can produce from your song listening history, playlist tabs, and so on.

Things I dislike about aTunes... well it's a Java app, so it takes a decade to start up. It also has horrid fonts and the widgets are clunky. But it's responsive once it's running, and I don't care how it looks as much as how sane the layout is. Searching is also clunky. But these aren't show-stoppers.

Here's a list of other players I tried, and why I didn't use them.