A phone call using G729 is not going to sound as good as a phone call using G711. G729 is a lower bit-rate codec.
That said, there could be a couple issues that are making the G729 calls sound worse, so you might want to investigate those. Check out this document for more info:
http://www.cisco.com/en/US/products/sw/voicesw/ps2237/products_tech_note09186a00801663a2.shtml
If most of your phone calls are coming in as G729, you probably want to avoid transcoding on the Unity server as much as possible, which would mean getting all the prompts, wav files, etc over to G729, as well as changing message storage format to G729. Check out this link if you haven't already:
http://www.cisco.com/en/US/products/sw/voicesw/ps2237/products_upgrade_guides_chapter09186a008022dfc2.html#wp1048893
One other note, if you are using a packetization interval other than 20 ms for your G729 calls - we did have a defect that made voice quality on those calls worse - see CSCed52913. If you upgrade to TSP 8.0(1) you'll get this fix.
I don't think the move to G729 alone will improve your audio quality problems, however you never know.