After trying songbird and being disappointed time after time, they finally make a version that works on my Vista.
Previously, the install would go well and then I was unable to load the program. Ever.

I am yet to try out the add ons (for adding lyrics, recommendations and album art) but thus far I'm just happy the window is up.

I should mention that the program hung for a LONG time before coming up, but once it did it runs fine. Screenshots below.