5v vs Vin

If I supply 5 volts (out of a computer power supply), what exactly are the differences between plugging into 5v vs Vin.
I didn't expect any difference, and since I know it is 5v, I figured the right thing to do was to plug it into 5v.

If 5v is connected and I turn the power supply on it puts the mega256 in some unknown state. If I then hit the reset button it works fine.
If the power supply is on, and I then connect to 5v, it works fine.

If I attach to Vin, it works either way.

What could be the issue? The power supply ramping up voltage/amps too slow or something?

Vin is the other side of the reverse polarity connection diode.

I often connect two Arduinos together by powering the second from the +5v of the first (ie. connecting both +5v lines together).

You might be right about the power supply ramping up too slowly. You could always use the +12v of the computer power supply and connecting it to the "power plug" (not Vin). Then the voltage regulator can do its stuff.

He could use Vin, that just bypasses the reverse protection diode.
That's legit. Regulator is still there.

ctwo:
If I supply 5 volts (out of a computer power supply), what exactly are the differences between plugging into 5v vs Vin.
I didn't expect any difference, and since I know it is 5v, I figured the right thing to do was to plug it into 5v.

If you have a regulated 5V supply, you should just connect to the 5V pin / node.

Vin has a regulator which supplies 5V to the 5V pin / node. The regulator needs >7V to properly regulate down to 5V. Putting 5V in will get you less than 5V out, leading to unstable operation.

I suspect the issue with the Arduino not starting up properly when the supply is powered up already connected is that it's not generating a good clean rising voltage at start up, only an oscilloscope can tell.

If the supply is a standard computer supply its designed to supply much more current than the Arduino takes, this could mean its not behaving within its specification with a much smaller load (Arduino takes about 50mA or so, computers usually take some number of amps).

Its always a good idea to measure any power source connected to the +5V pin since overvoltage here will fry the board, whereas Vin has a regulator that helps to protect the board.