I have run into this problem many times. The thing is that just because the phone can play/record AMR/WAV/MP3 and so on, doesn't mean it can do it in Java. Even if the phone is stated to support MMAPI it doesn't have to support all the formats. For example the Nokia 6230 (a fairly advanced phone) can only play tones and MIDI files in MIDP apps!
Remember, the implementation of MIDP (and MMAPI) varies from one Nokia phone to another and has nothing to do with its listed playback/record support.
Here is some quick code to test MMAPI formats supported on a Nokia phone, place it in a keypress event: