My suggestion is to scrap the 12V wall wart unless you need it for some other purpose and use a 5V regulated wall wart. That saves you some work. If you do need 12V for other purposes, you may want to look into a dual output wall wart. These normally use much more efficient switch mode supplies internally. If you use a linear regulator to drop 12V to 5V, you burn more power in heat in the regulator than you deliver to the load! Don't use a pot for this purpose. The power dissipation will be high, and regulation will be very poor (i.e. non-existent beyond what you set). Also, the voltage at the wiper of the pot will vary slightly with load, i.e. as you turn LEDs on and off.
My suggestion is to use a single pot bridged between GND and 5V as your "knob of doom". Hook the wiper directly up to the A/D input on your microcontroller. Make sure you keep the pot below 10k, otherwise you'll need an analog buffer (aka voltage follower) to keep sample/hold times reasonable. A 1k pot should work well and will only have 5mA going through it. The input impedance on the micro's A/D input (at least the AVRs you're talking about - I like your micro choice, btw) is fairly high, so you don't have to worry about current being drawn off the wiper. Digitize that, divide it up into levels, then use IOs to drive your LEDs.
For driving the LEDs, you may be able to get by with driving it low-side (LED anode at 5V, through a resistor, to the uC I/O line) directly off the I/O lines. Check your desired LED current vs. the I/O max sink current. If you have bright LEDs and need more current, there are several options out there that are transistor arrays usually 7 in a package. Something like the MC1413 which is even available with base resistors to let you drive it directly off your uC I/O lines (in this case, logic high would be LED on).
Since you have reasonably small LEDs that are well characterized, you don't really need the dedicated constant current driver. You can of course use it if you want to, but a simple resistor to set the current is probably easier.
If you use output compare (timer) channels on your micro, you can even PWM the LEDs to set brightness.
The other way to do this is with a bunch of comparators. The functionality is the same, but you're using analog electronics rather than digitizing the pot position and making decisions that way. The uC solution also lets you do "attract mode" if you want (yet another use for brightness control).