I am the client mentioned above.
It was the network speed. All of the new computers we were getting in had gigabit network cards. Even though the switch is only 100Mb, I'm guessing that when Windows started up or shutdown the NIC, that it send some sort of auto-negotiate signal that the Mitel phones did not like.
I went to Device Manager and set the NIC to 100MB Full Duplex instead of auto negotiate and it fixed the problem. Thank you guys!
I'm going to go test this on another machine with a 5220 doing the same thing just to verify that the fix can be duplicated.