Arduino duemilanove not working

You'd want 50V caps on the input side of 9V regulator, 25V or 16V caps everywhere else.
10uF/1uF for 9V, and 1uF/1uF for the 5V would work fine.