Factory default the phone
Delete the PBX extension configuration
Restart the phone server
Reconfigure the phone and the pbx extension

Registration of a SIP phone is a relatively simple process. There are not that many things that can go wrong. To register a SIP phone, you need
1. Network connectivity between the phone and the server
Considering the server displays registration errors, this is okay.
2. On the phone, you must correctly configure the host name or IP address of the server and the SIP signaling port number
Again, based on the fact you're seeing registration errors, this is okay, too.
3. On the server, if you use Permit/Deny for SIP extension for security reasons, the permit rule must match the phone's IP address
If this was wrong, you would get an ACL error and not a wrong password error.
4. On the phone, you must correctly configure the user name and secret to match an extension configured on the server.
Based on the error you're getting, one of these is wrong. You claim that you checked/changed the password multiple times. I guess that leaves the user name (which should be set to the extension number).

I don't think you will convince the phones to register using a baseball bat...

Over the years, I've seen many different phone issues (wont register, can't be called, goes straight to VM, won't forward to VM on busy,etc.). After trying all the normal trouble shooting steps, I found that deleting the extension and adding it back resolved the issue.
Just my 2 cents.

I spoke with emetrotel about the issue and they reccommended that I reset the phone to factory defaults and start over. I brought one of them home and connected it to my network, reset it to default, connected it to a new UCX, updated the firmware to the latest from Polycom and programmed it as per their document and the set registerd immediately and stayed registered so that is what I will do with the ones at the customer site tomorrow. We'll see how it goes.

Emetrotel was very helpful when I spoke with them.

Glad its working.
For grins and giggles before you update the other phone firmware at the customer location
default the phone and delete the pbx extension
reprogram both the phone and extension