I have successfully tried MP3 with 128 kbps 44100 Hrz Stereo and 64kbps 44100 Hrz Mono. Just had to cut them to be no bigger than 507k. On Linux it looks like this:
mpgtx -s your.mp3 [-507k] -o ringtone.mp3
One can play with the value in brackets to get the desired part of the mp3, e.g. [1000k-1507k] would also do.
Just in case, "lame -cbr -b 128 -m m -q 1" produced compartible output mp3.