Попробуйте закодировать 256 кбит/сек (хотя вряд ли из-за этого не работает), и не Joint Stereo, а моно.
Может, телефон смущают русские тэги. Что ещё предположить-то?
Есть ещё программка для анализа аудиофайлов -
Mr. QuestionMan. Возможно, она покажет что-то ещё, например, какой библиотекой был закодирован первый файл.
