I have VVX300 phones using that same firmware version without issue, so it may be something else weird with the registering. You might turn on the Protocol Capture and Syslog functionality under Diagnostics on the Phone Trunk and reproduce the problem, then see what those logs show (if anything).
A Reset to Factory might kickstart the phones, too...wouldn't hurt to try it on one.
PureCloud Voice or local Edges? I forgot to ask.
------------------------------
George Ganahl CCXP, GCA
Principal Technology Consultant
Genesys
------------------------------