Arduino circuit/breadboard not working at higher voltage?

Not wrong, just not very effective.

The parts I am talking about on the schematic are:
PC1, PC2, these are like the 22uF cap you have by the regulator now. That is good. Get another one of those.
See figure 1 here:

100uF might be overkill, but it won't hurt. I've been using 1uF on the input and 0.47uF on the output, but only because I had a bunch on hand.

Move the little cap across pins VCC & GND over by the crystal the way that C6 is connected up.
Wire up a current limit resistor the way that RN2A is connected.