Causes and solutions "UIDs on system are inconsistent... I'm feeling lucky"?
A Solution

On reflection, my thoughts were 1) this seems like a software problem, possibly malware of unknown origin and 2) it seems to be interrupting the power-cycling of the phone.

Therefore, before committing to sending the phone out to either HTC or Vodafone to look at, i tried my own hard-reset of the phone.  Without access to remove the battery, i simply discharged the battery completely (wifi,GPS,Bluetooth,NFC,active call).

Now, plugging in the phone to charge, i found that i could enable a hard reset (holding down power and volume down) i get a basic text interface with option to do a hard reset.  This was sucessful.  Clearly this is a much stronger version of the factory reset than via the menus.

My phone is now set up again and working happily, and i dont need to send if off for "repair".

Possible causes

My feeling is this was a piece of malware, although i have no direct proof.  As a resource to assist others, below i list the most recent apps i downloaded.
/Trigger: SMS Plugin/NFC ReTag FREE/No One Dies/Rightmove Property Search/Contacts Optimizer/Google Keyboard/AnyTag NFC Launcher/Proxy Settings/Aix Weather Widget/Bright Weather/

In hindsight, i accept that some of these are from lesser-known sources, albeit all acquired via the play store, i didn't pay close attention to the permissions.

Summary

My primary motivation for posting here is because i failed to find useful advice yesterday when i needed it.  Many others have posted about this message, some also suspecting malware, but most say a factory reset solved the problem.  I hope to add to the situation the following new pieces of information

1) Eject and reinsert of the SIM card to proceed when frozen

2) Running the battery down as a method of doing a hard reset, if the other method fails

3) A list of apps i recently downloaded, might help point towards a possible source of malware, albeit useless until compared with other users who encounter the same problem.