I've tried all the VOIP the app store currently has to offer: Truphone, Fring, and PennyTel and with the exception of Truphone, the others suck big time when it comes to call quality. Fring(skype) and PennyTel both suffer from frustrating lags, echoes etc making them almost unusable. Fring especially was a big dissapointment for me. Truphone was problematic at first when I can't get a connection, but it seems they've improved their backend support and the calls are going through with reasonable quality. The only gripe I have is that there is no support to take incoming calls on Truphone yet.
Hopefully iCall will not be a dissapointment when it finally makes to the app store.