FlashFormat by CNETX will format both CF and Sd cards.
Do you have many things running while trying to use Windows media Player? Also how long are the mp3s, what bitrate(may be too low of bitrate possibly)?
I don't have any problems with mp3s and I usually have like 1 or 2 hour DJ mix shows in mp3 format that I listen to with the axim. Am using Sandisk SD and CF card as well, with no problems mysteriously.