OK so a couple of things , lets get your phones totally cleared of any other settings ,you mention your utility server has potentially got corrupt files on , lets delete those files get to support,avaya.com get the latest firmware for your sets and get it on utility server , then lets patch utility server , then lets reboot utility server .... or sack it off and use mviptel or IIS until you can be sure its working as planned.Utility server can be a little horrible , im just about to knock off shift but main things
Compatibility matrix ... is CM & SM on supported versions ..... is the system platform hosting these machines current and patched.
Phones .... can you go from the version you are trying to the version you want(again compat matrix)
46xx settings file , procstat allows local admin of the phones ( it sounds like you have some phones that have different procstat settings or passwords set)
Try to mute craft the phones and clear the values then .patch ...get working firmware for your hardware and try a one phone that was not working first and build up.
Here is a link to the most recent lan admin guide for sip phones...... if you need any more help im sure other forum members will assist but im sure this is something pretty simple that your Avaya BP should be able to help with
I wish you well but this sounds like somebody has left you in the lurch.... i will be happpy to try and assist tomorrow if not resolved when i come back on line
APSS (SME)
ACSS (SME)
ACIS (UC)