So knowing the above, I went into the phone config GUIs and made some changes with the codec priorities, but without making any changes to the PBX. The Mitel always properly negotiated audio, always using g722 (when configured) regardless of what I set the codec order to, and if g722 was not configured it would properly use ulaw. The GS phone would NEVER negotiate codecs properly if the phone codec list included both ulaw and g722 in any order. The only way to get audio to work was to force all codecs to either ulaw or force all to g722, in each of these circumstances, audio worked.