I really liked Amarok, an upgrade to ubuntu brought in Amarok 2. I couldn't get it to play anything and it was quite unpleasant to use. Luckily I managed to find a fix and my playlist was populating within seconds and music was playing - the fix is called Rhythmbox