You might like my very old AVR-based binary clock project:
I had the same irritation at the binary coded decimal representation on the ThinkGeek binary clock, so I made mine with just three binary registers. The binary coded decimal representation has the advantage of generating more interesting patterns though.
As far as time-keeping, the simplest way is to use a board that supports an RTC.
There are shields like this one:
that have everything in one package, including buttons for setting the time and a beeper for chimes/alarms (also temperature module, light sensor and several LEDs). For a binary clock project you can use the on-board display for other purposes (debugging, user interface, whatever), or just remove it. However, it would make getting to the pins you need for your led display a little more difficult, and you get a bunch of stuff you don't really need.
A more targeted, cheaper and smaller RTC-only module such as:
would probably be a better choice. There are many similar options, but I'd recommend picking one with the included battery so that your clock retains time through power disconnections.
Most of these RTC modules will drift a fair amount. This is because not much effort is put into preventing temperature-based variation of the crystal resonant frequency. If you want it to keep time better you'll need to pay for a module that is higher tech than what you'll find in the $2 price range, or use an external signal for sync (GPS, power line zero crossings, radio WWV, etc). A silly hack might be to use a cheap digital watch with an alarm set to midnight. Connect the alarm signal to an arduino input, and resync when you get the alarm.
You should check out neopixel LEDs for your display. Lots of RGB LEDs arranged however you want with only one data line to drive the whole thing. Very bright, versatile, and good for animations and such. Available in strips and panels. Costs more than bare LEDs, but they are reasonable, the additional capability and easy of use may be useful for you.