Most of the recent NOKIA phone (and specifically all of the 3rd generation ones) supports playing music.
The main issues are how much memory the phone has and does the phone supports adding an external memory of some kind (MMC, SD, etc).
Since most of the new phones do support playing music, you should also consider other features, such as PIM (personal information management), Email support, Internet browsing support, etc.
If I'd have to choose, I would choose the NOKIA 6230i for a non 3G phone. For a 3G phone, I would go with the N70 or N73. But that's just me