Funny you posted this... I've been thinking/planning about doing the same thing

(and I'm sure there are quite a few more out there.) My dilemma however has been the loss of all the data pins on the board due to all the digital pins needed by the Arduinix board. I ended up getting a Arduino Mega as I needed more pins, but haven't decided if I'm going to use it yet or not (more as you read on...) I found a VERY basic example on how to decode time (works most of the time) using this from Digikey -
http://search.digikey.com/scripts/DkSearch/dksus.dll?Detail&name=561-1014-ND that looks like from your Edit you already found. Essentially it reads the pulse output on a single digital pin, and then decodes the time (search for Arduino and CMMR-6P-60 and you'll find a ton of code.) I will say the 60mm antenna didn't work at all for me in Massachusetts (though most atomic clocks don't work well here...) But I ended up ordering an antenna on eBay from a ham in CT, and it works very well, though it's a bit big at 2' so not overly practical... I also have a fairly pricey board I had ordered out of the UK for decoding WWVB, but the cheap one from Digikey by far can't be beaten for the price.
My plan B is actually the same as yours thinking of going GPS. On the Arduino Diecimila there are two serial data pins (0 and 1) and in theory you could get away with just the pin 0 for RX from a GPS. I believe I read somewhere it will talk direct TTL so you can get one of the OEM modules from Sparkfun or other vendors. I haven't figured out which one I want to try out yet, it's on my list of projects. I'd probably get one of the modules that will take an external antenna to give it a bit of a boost as I want to make a clock for my office. I will say most of the newer chipsets, even inside a building WILL lock a GPS signal without a problem.
Ideally I'd love to use NTP as plug and play. But again it goes back to my original problem of not enough data pins to get this done... I was toying with the idea of making a custom board based on the WizNet platform, but not sure if I can feasibly move all the pins in the code and have it still work. I am a bit biased for NTP as I am currently building an NTP server based on the Soekris NET4501 with it's crystal replaced, that also uses a special GPS for doing time sync,
http://www.febo.com/pages/soekris/ . Too many project, so little time and money

Another (non-related idea) was using a pin and a timer (whether in software, or via a timing relay) connected to a motion sensor. This way I can have the tubes shut off if I am not there to save their life, but the clock itself can keep the time.
I'll probably post as well what I ended up doing. Right now my first challenge is designing how I want to mount my IN-18 tubes. Not sure if I can find a premade board to buy, to make my own board.
-Mike
So does the mega work then with the Arduinix? If so using that and then the Cmax chip sounds like a great solution although not a cheap one. I know this project will end up costing me more than I was originally thinking but it will be cool once im done so Im ok with that. I think this would be a good solution for me then since I am not familiar with the code. I could probably get someone to integrate the 2 batches of code into one working project.
As for the antenna Cmax sells a larger unit that I read about on a few blogs and people report having alot better luck with it. Its also cheap $2.10
http://search.digikey.com/scripts/DkSearch/dksus.dll?Detail&name=561-1001-ND People just take the copper off this one and put it on the one it shipped with to have the package be a little smaller.
What I am concerned about is potential noise from the tubes causing interference on the radio receiver. I read about how some people had alot of problems with this.
Its funny you posted all of this because in my dream clock I dont think I would have a motion detector but rather a simple switch on the back that would allow me to turn the display on and off yet still keep the clock going, to both save tube life and make the room dark at night.
I think I am going to get my clock built and working and then work on the case because who knows what size and form this thing will end up taking. I hate to buy/build a nice case and not have it fit.
Keep in touch about your project I am very interested in it.
I just found this and wonder if this is the way to go
http://www.amug.org/~jthomas/wwvb.html