FYI Fring now allows calls over 3G natively.
I tried Fring, and it was unusable, sound quality was terrible, and there was literally a good 4-5 seconds delay. I would not recommend it at all ( At least from my experience) This was between an iPhone to an iPhone Fring conversation (without using the 3G unristirctor) from Toronto to NYC (Rogers to AT&T) both on the 3G network, right after we hung up and used Skype and sound was crystal clear.
I've tried this a few times and it sounded terrible for me—and if I am driving I have to plug in my headphones because BT doesn't work with it. At least you got it working.
That's right Bluetooth Doesn't work with Skype or with Fring or any similar apps. But while I'm mountain biking, I cannot rely on a bluetooth piece dangling off my ear, I use stock blackberry earphones. I find them to be the most reliable, also with good sound quality (for talk and music) much better than the iPhone stock earphones.
Of course there are probably much better aftermarket iPhone earbuds (headphones etc.) but I got these Blackberry earphones from my cousin who never thought she'll have a need for them, and I haven't looked elsewhere since.
As far as Skype's sound quality, it sounds crystal clear to me, you have to remember the sound quality of a Skype conversation very much depends on the connection and the setup of both parties. if you are calling a person on their desktop or laptop Skype. it's best that they at least have their headphones on too, once you start hearing (feedback) your own voice on the other end, quality is effected greatly.