Hi Paul, those do sound strange errors. I seem to remember in my very early days I had an issue with the locale message but actually the message was a red herring and had nothing to do with the actual problem which was registration so you may find you're experiencing the same thing.
You must have a t*f*t*p server running otherwise the other two wouldn't run. I'm pretty convinced this is a registration issue. Here's what I would try step by step:
1 - check username and password. I've stared at a screen so long before I haven't noticed one tiny error and it could be something as simple as this. I have a secure password but because my handsets are all on a small home network they all share the same password and I only change the username. You should check your config file and FreePBX extension screen.
2 - check your phone has the right address for t*f*t*p via the settings button on the handset. Possible the surge knocked a stored setting out so you need to tell the handset where the t*f*t*p server is.
3 - as Brian suggests is TCP enabled on all handsets? Remember you need to have tcpenable=yes in your additional settings on FreePBX, TCP on your extension screen, and your config file must be configured to use TCP as the transport (check my Cisco guide in the resources section for what number you need as transport, I think it's 1 in the latest firmware off the top of my head).
I'm suspecting NAT isn't a problem at the moment. If you get really stuck then take a known good config file, copy it and rename it to the MAC of one of the handsets you're having problems with. If this lets you on then you know there's a problem with your config file, if it doesn't you know the problem is somewhere else.
And as a final piece of advice - don't give up, have patience and if you're feeling overwhelmed walk away and take a break. It's rare these phones get damaged in power surges and that you have 2 suggest to me it's a setting somewhere rather than a hardware fault so I reckon you're likely to get to the bottom of this with a little help from us.