Is 600kpbs upload speed too slow for VOIP app?

Is 600kpbs upload speed too slow for VOIP app?

I've built a voip app for iphone and android phone (audio only). I've been
testing the call quality. I noticed that if a person has an upload speed
of less than 600kbps, then his partner will have trouble hearing him
clearly. His partner might hear lots of crackling, dropped sentences in
speech, or nothing at all.
I am currently using GSM codec on my android, iphone and on my asterisk
server.
So my question is whether upload speeds of less than 600kpbs is generally
considered too slow for VOIP calls?
If so, is there anything I can do to reduce necessary bandwidth for call?
I could consider the G722 codec, but from what I remember, it doesn't
offer significant bandwidth improvement compared to GSM