I talked to a buddy of mine who suggested that it sounds like this was being caused by power supply problems. I took the Nixie Clock apart and noticed that the big blue super capacitor had oily droplets on top of it. Apparently, this is a classic case of capacitor plague and the supercap had to be replaced.
This supercap is a 0.33F 5.5V capacitor. I went down to Jaycar, needless to say they had nothing anywhere near close to a capacitor with that rating and form size (13mm diameter, 6mm height). Eventually I found some of these on eBay in Germany and snapped up 5.
After a couple of weeks they arrived...
I went ahead an desoldered the old one, here is a picture of the old and the replacement sitting together, you can see some corrosion on the bottom of the blue cap. I had a photo of the top, but it didn't clearly show the oil drops so I left that out.
The new cap was a perfect fit to my surprise.
After putting the clock back together and setting the time, unplugging the power and plugging it back in (I tried this a few times), it started to act a bit better...at least it didn't reset the time. I'm still having GPS issues with it, I think that could be the receiver but haven't had time to investigate in more detail yet.