It's important to note that this on-the-fly conversion does not alter your original files inside your iTunes library -- those will remain at whatever bitrate and in whatever file format you had them in.
How well does this work? I saved a whopping 1.5GBs of space on my 8GB iPhone. Others here at TUAW saved between 2-5GBs. Of course, how much space you save will be dependent on what bitrate and file type your songs are now. The guys here who saved 5GB said their conversions took a few hours initially. As for audio quality. I didn't notice a bit of difference on my $20 headphones. However, I'm not an audiophile. If you've got an ear for music and are using the latest Shures, you might notice some quality degradation.