I'm not really sure what's going on either. I've only got one idea and it's a shot in the dark, but:
Make sure that you're not clicking the big green "Send to Phone" button. I know it looks like it makes things one-click easy, but it doesn't. It's just an advertisement. You need to click the small blue links under the star rating that say "MP3/WAV/M4R" and choose the format your phone uses.