Psu / case combos are tempting, but as this is your first time it wont be your last ! its a fun process you will surely enjoy.
Get a case you like the look of, get a powersupply you see good reviews of ! , a Psu is for life not just for christmas, i personally am an advocate for buying the psu that will cost more but outlast everything else in the pc, a good corsair 550W or 600W would be closer to your needs 450W leaves little room to maneuver in the future.
Good cpu choice, perhaps overkill, maybe the same model black a few steps back will clock as high as that one, but cost you less, im not sure i'll leave it up to other commenters to answer that.
Ubuntu should have no trouble using the latest nvidias or ati cards. It should prob just come down to brand loyalty and comfort for your case, you havent suggested a card like you thought you had , but for a system under a budget id get a 460 or a 5770, again at your preference. Decent cpu cooler, might perhaps need one stronger for that amd, im not sure.
Assembly is a cake walk, buy all your parts retail and everything has an instruction book, dont forget the Lube for your cpu though

good thermal paste is always good to have for 6 pounds.